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
for Slowsort is
.
A lower
asymptotic bound for
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
for any
.
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