Slowsort

Last updated

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 ). It was published in 1984 by Andrei Broder and Jorge Stolfi in their paper "Pessimal Algorithms and Simplexity Analysis" [1] (a parody of optimal algorithms and complexity analysis ).

Contents

Algorithm

Slowsort is a recursive algorithm.

This is an implementation in pseudocode:

procedureslowsort(A[],start_idx,end_idx)// Sort array range A[start ... end] in-place.ifstart_idxend_idxthenreturnmiddle_idx:=floor((start_idx+end_idx)/2)slowsort(A,start_idx,middle_idx)// (1.1)slowsort(A,middle_idx+1,end_idx)// (1.2)ifA[end_idx]<A[middle_idx]thenswap(A,end_idx,middle_idx)// (1.3)slowsort(A,start_idx,end_idx-1)// (2)

An unoptimized implementation in Haskell (purely functional) may look as follows:

slowsort::(Orda)=>[a]->[a]slowsortxs|lengthxs<=1=xs|otherwise=slowsortxs'++[maxllastrlast]-- (2)wherem=lengthxs`div`2l=slowsort$takemxs-- (1.1)r=slowsort$dropmxs-- (1.2)llast=lastlrlast=lastrxs'=initl++minllastrlast:initr

Complexity

The runtime for Slowsort is .

A lower asymptotic bound for in Landau notation is for any .

Slowsort is therefore not in polynomial time. Even the best case is worse than bubble sort.

References

  1. Andrei Broder; Jorge Stolfi (1984). "Pessimal Algorithms and Simplexity Analysis" (PDF). ACM SIGACT News. 16 (3): 49–53. CiteSeerX   10.1.1.116.9158 . doi:10.1145/990534.990536. S2CID   6566140.