Slow sort

SlowSort (. Of English slow : slow) is a slow, recursive sorting algorithm , which according to the principle Multiply and surrender (Engl. Multiply and surrender , a parody of divide and rule ) works. It was presented in 1986 by Andrei Broder and Jorge Stolfi in their (not entirely serious) publication Pessimal Algorithms and Simplexity Analysis .

principle

Slowsort is a recursive algorithm that works in the following steps:

1. Determine the maximum of the field to be sorted and place it at its end.
2. Sort the remaining field by calling the algorithm itself recursively.

The first step is divided into several slightly simpler steps according to the principle of multiply and surrender :

• Find the maximum of the first half of the field to be sorted: Choose the last element of the (recursively) sorted first half.
• Find the maximum of the second half of the field to be sorted: Choose the last element of the (recursively) sorted second half.
• Find the maximum of the two submaxima.

This is repeated recursively until the subfield only contains a single element and the solution cannot be delayed any further.

 procedure slowsort(A,i,j)                            // Sortiert das Array A[i],...,A[j]
   if i >= j then return
   m := floor((i+j)/2)                                // abrunden, falls i+j ungerade
   slowsort(A,i,m)                                    // (1.1)
   slowsort(A,m+1,j)                                  // (1.2)
   if A[j] < A[m] then vertausche A[j] und A[m]       // (1.3)
   slowsort(A,i,j-1)                                  // (2)

The first five lines of the pseudocode do not differ from mergesort , and only the merging of the two sorted subfields is done (instead of an efficient merging) by an extremely inefficient recursive call.

The correctness can be shown relatively easily by complete induction on the number of elements.

Furthermore, Slowsort is not a stable sorting process : When entering (1, 3, 2a, 2b), 3 is swapped with 2b at the first recursion level. In the further course of the process, no further interchanges take place, so that Slowsort terminates with the output (1, 2b, 2a, 3).

complexity

The running time for Slowsort satisfies the recursion equation . A lower asymptotic limit for expressed in Landau notation is for any . The algorithm is therefore not polynomial . SlowSort is therefore also in the best case such as inefficient. B. Bubble sort with a complexity of . ${\displaystyle T(n)}$ ${\displaystyle T(n)=2T(n/2)+T(n-1)+1}$ ${\displaystyle T(n)}$ ${\displaystyle \Omega \left(n^{\frac {\log _{2}(n)}{(2+\epsilon )}}\right)}$ ${\displaystyle \epsilon >0}$ ${\displaystyle {\mathcal {O}}(n^{2})}$

Number of swaps

In contrast, Bubblesort needs at least as many swaps as Slowsort. A measure of how “strongly” a field with elements differs from the sorted field is the number of missing items , that is, the number of pairs with which applies. ${\displaystyle A}$ ${\displaystyle n}$ ${\displaystyle (i,j)}$ ${\displaystyle 1\leq i<j\leq n}$ ${\displaystyle A[i]>A[j]}$

When swapping with Bubblesort, the number of missing items is reduced by exactly one, while with Slowsort it is reduced by at least one (by exactly one if all values ​​in the field are different). The number of missing items is therefore an upper limit for the number of slowsort swaps, since exactly one sorted field has no missing items. The maximum number of interchanges in a field with elements is therefore maximum with Slowsort and precisely when it is sorted in descending order. Therefore, within a recursive call, an interchange takes place only in the rarest of cases. ${\displaystyle n}$ ${\displaystyle \textstyle {\binom {n}{2}}}$

Web links

• Scientific publication by Broder and Stolfi