HOME

TheInfoList



OR:

Slowsort is a sorting algorithm. It is of humorous nature and not useful. It is a ''reluctant algorithm'' based on the principle of ''multiply and surrender'' (a parody formed by taking the opposites of ''
divide and conquer Divide and rule policy ( la, divide et impera), or divide and conquer, in politics and sociology is gaining and maintaining power divisively. Historically, this strategy was used in many different ways by empires seeking to expand their terr ...
''). It was published in 1986 by Andrei Broder and Jorge Stolfi in their paper ''Pessimal Algorithms and Simplexity Analysis'' (a parody of '' optimal algorithms'' and '' complexity analysis'').


Algorithm

Slowsort is a recursive algorithm. * It sorts
in-place In computer science, an in-place algorithm is an algorithm which transforms input using no auxiliary data structure. However, a small amount of extra storage space is allowed for auxiliary variables. The input is usually overwritten by the output ...
. * It is a
stable sort In computer science, a sorting algorithm is an algorithm that puts elements of a list into an order. The most frequently used orders are numerical order and lexicographical order, and either ascending or descending. Efficient sorting is importan ...
. (It does not change the order of equal-valued keys.) This is an implementation in pseudocode: 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 nd_idx< A iddle_idxthen swap (A nd_idx, A iddle_idx // (1.3) slowsort(A, start_idx, end_idx - 1) // (2) * 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 Haskell () is a general-purpose, statically-typed, purely functional programming language with type inference and lazy evaluation. Designed for teaching, research and industrial applications, Haskell has pioneered a number of programming lan ...
(purely functional) may look as follows: slowsort :: (Ord a) => -> slowsort xs , length xs <= 1 = xs , otherwise = slowsort xs' ++
ax llast rlast An axe ( sometimes ax in American English; see spelling differences) is an implement that has been used for millennia to shape, split and cut wood, to harvest timber, as a weapon, and as a ceremonial or heraldic symbol. The axe has many ...
-- (2) where m = length xs `div` 2 l = slowsort $ take m xs -- (1.1) r = slowsort $ drop m xs -- (1.2) llast = last l rlast = last r xs' = init l ++ min llast rlast : init r


Complexity

The runtime T(n) for Slowsort is T(n) = 2 T(n/2) + T(n-1) + 1. A lower asymptotic bound for T(n) in
Landau notation Big ''O'' notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. Big O is a member of a family of notations invented by Paul Bachmann, Edmund Land ...
is \Omega\left(n^\right) for any \epsilon > 0. Slowsort is therefore not in
polynomial time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
. Even the best case is worse than
Bubble sort Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the input list element by element, comparing the current element with the one after it, swapping their values if needed. These passes ...
.


References

{{Sorting Computer humor Sorting algorithms