Slowsort

Slowsort is a deliberately inefficient sorting algorithm of humorous intent, not useful for practical applications. It is a reluctant algorithm built on the principle of multiply and surrender, a parody formed by taking the opposite of divide and conquer, and it was published in 1984 by Andrei Broder and Jorge Stolfi in their paper Pessimal Algorithms and Simplexity Analysis, itself a parody of optimal algorithms and complexity analysis. The method is recursive and sorts in place, and it is unstable, so it may change the order of equal-valued keys. It sorts the first half and the second half recursively, compares the two results to find the maximum of the whole array and places it at the end, and then recursively sorts everything except that maximum. Its running time follows the recurrence T(n) = 2T(n/2) + T(n-1) + 1, which gives a lower bound that grows faster than any polynomial, so Slowsort is not in polynomial time.