Slowsort

Slowsort is a recursive algorithm. • It sorts in-place. • It is an unstable sort. (It might change the order of equal-valued keys.) A pseudocode implementation is given below: procedure slowsort(A[], start_idx, end_idx) // Sort array range A[start ... end] in-place. if start_idx ≥ end_idx then return middle_idx := floor( (start_idx + end_idx)/2 ) slowsort(A, start_idx, middle_idx) // (1.1) slowsort(A, middle_idx + 1, end_idx) // (1.2) if A[end_idx] • Sort the first half, recursively. (1.1) • Sort the second half, recursively. (1.2) • Find the maximum of the whole array by comparing the results of 1.1 and 1.2, and place it at the end of the list. (1.3) • Sort the entire list (except for the maximum now at the end), recursively. (2) An unoptimized implementation in Haskell (purely functional) may look as follows: slowsort :: (Ord a) => [a] -> [a] slowsort xs | length xs ==Complexity Analysis==

The time complexity of Slowsort is given by the function T(n) = 2 T(n/2) + T(n-1) + 1. It can be found by creating a recurrence relation of the initial recursive calls (1.1) and (1.2) respectively and summing the final recursive call (2) and modelling the other operations as a constant (+1) in this case. This gives a lower asymptotic bound for T(n), which in Landau notation is given as \Omega\left(n^{ \log_2(n)/(2+\epsilon)}\right) for any \epsilon > 0. Therefore Slowsort is not in polynomial time. ==References==