Slowsort

Uses your system voice; voice and rate in settings.

Snapshot

≈ 2 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

Slowsort is a sorting algorithm. It is of humorous nature and not useful for practical applications. It is a reluctant algorithm based on the principle of multiply and surrender (a parody formed by taking the opposites of divide and conquer). It was published in 19841 by Andrei Broder and Jorge Stolfi in their paper "Pessimal Algorithms and Simplexity Analysis" (a parody of optimal algorithms and complexity analysis).

Slowsort is a sorting algorithm. It is of humorous nature and not useful for practical applications. It is a reluctant algorithm based on the principle of multiply and surrender (a parody formed by taking the opposites of divide and conquer). It was published in 1984 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. 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

Text derived from https://en.wikipedia.org/w/index.php?oldid=1374390618 under CC BY-SA 4.0; modifications have been made.

References

  1. ↩Wikipedia “Slowsort” revision 1374390618 · retrieved 2026-10-20 publication date (×1) · confidence 0.95 revision URL

Provenance

snapshot enwiki-001374390618 · captured 1789148533.0 · version history

Cite this page as: encyclopegia.org, “Slowsort”, snapshot enwiki-001374390618. https://encyclopegia.org/a/slowsort