Recursion – Slowsort

Some algorithms were never meant to be important, or efficient, they just exist. Slowsort is one of those algorithms, thrown into the ether for some reason. The algorithm was published in 1986 by Andrei Broder and Jorge Stolfi in their paper Pessimal Algorithms and Simplexity Analysis [1] where they explored a series of sub-optimal algorithms. The authors described it as an “elegant recursive algorithm“. The slowsort algorithm is a good example of what is termed the multiply and surrender paradigm.

The algorithm consists of sorting n numbers, A1, A2, …, An into ascending order following this simple algorithm: (i) find the maximum of the numbers and (ii) sort the remaining numbers. The first part of the algorithm can be further decomposed:

1. Find the maximum of the list containing the first 1..n/2 elements.
2. Find the maximum of the list of remaining n/2+1..n elements.
3. Find the largest of the two maxima, which is placed at the end of the array.

Steps (1) and (2) can be solved by sorting the specified elements and taking the last element in the result. The original problem has then been multiplied into three simpler ones: (i) sort the first half; (ii) sort the second half; and (iii) sort all elements but one. This is continued recursively until the lists have at most one element, at which point the algorithm surrenders. Here is the complete algorithm:

subroutine slowsort(A, i, j)
   if (i ≥ j) then
      return
   else
      m = abs((i+j)/2)
      slowsort(A, i, m)
      slowsort(A, m+1, n)
      if (Am > Aj) then
         swap(Am,Aj)
      end-if
      slowsort(A, i, j-1)
   end-if
end-subroutine

The lower bound of Slowsort is non-polynomial in nature and for a sufficiently large value of n this would be more than n^2 implying that even the best case of Slowsort is worse than the worst case of Bubble sort. Even running this code in C is slow. We tested it using 500 randomly generated integers. The Bubblesort took 0 seconds, while the Slowsort took 476 seconds. Not amazing (and trying it with a larger dataset isn’t even worth it).

A brief note on Multiply and Surrender

A basic multiply and surrender (MaS) problem solving paradigm consists of replacing the problem by two or more subproblems, each of which is marginally simpler than the original. The subproblems and subsubproblems are multiplied continuously in a recursive manner. At some point the subproblems will become so simple that they must be resolved, and they will “surrender”. This is similar to divide-and-conquer, however MaS procrastinates, making the entire process very inefficient, even though it does converge.

[1] Broder, A., Stolfi, J., “Pessimal Algorithms and Simplexity Analysis“, ACM SIGACT News, 16(3), pp.49-53 (1984)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.