Slowsort - a pessimal sorting algorithm

Slowsort is a sorting algorithm that is designed to be deterministically sub-optimal. The algorithm was published in 1986 by Andrei Broder and Jorge Stolfi in their paper Pessimal Algorithms and Simplexity Analysis where they expressed a bunch of very in-efficient algorithms. These techniques and algorithms are special because they never make a wrong move while solving a problem, instead, they find ways to delay the success. In this essay, we put our focus on the Slowsort algorithm based on the Multiply and Surrender paradigm.

Multiply and Surrender

The Multiply and Surrender (MnS) paradigm, is a humorous take on the popular Divide and Conquer (DnC) technique. MnS splits the problem into subproblems, slightly simpler than the original, and continues doing so recursively for as long as possible. The subproblems are multiplied and the evaluation is delayed till the state that the solving could not be further postponed and then it surrenders.

MnS paradigm is very similar to DnC; but where the DnC actually splits the problems into subproblems to reach the solution quicker, MnS does it to procrastinate, making the entire process very inefficient but yet convergent.

Although Slowsort is a classic example, recursive Fibonacci with no memoization also fares under the MnS paradigm. The recursive code to find nth Fibonacci number is as illustrated below

While computing the Fibonacci numbers, we split the problem into subproblems and do this recursively till we are left with elemental states i.e. 0 or 1 and which is when we return the initial values which are 1 and 1. This approach is not DnC because we are not splitting the problem into subproblems to achieve optimality, instead are doing a lot of repetitive work and taking a non-polynomial time to generate the Fibonacci numbers.

Slowsort Algorithm

Slowsort algorithm draws a lot of similarities to the very popular Mergesort, but while Mergesort operates in O(n . log(n)) the complexity of Slowsort is non-polynomial O(n ^ log(n)) and its best case performs worse than the worst case of bubble sort.

Slowsort algorithm recursively breaks the array sorting problem into two subarray sorting problems and a few extra processing steps. Once the two subarrays are sorted, the algorithm swaps the rightmost elements such that the greatest among the two becomes the rightmost element of the array i.e. the greatest among the two is placed at the correct position relative to each other, and then it invokes the sorting for all elements except this fixed maximum.

The algorithm could this be expressed as following broad steps

  • sort the first half recursively

  • sort the second half recursively

  • find the maximum of the whole array by comparing the last elements of both the sorted halves and place it at the end of the array

  • recursively sort the entire array except for the maximum one

The in-place implementation of the Slowsort algorithm is as illustrated below

The Slowsort algorithm typically replaces the merge function of the Mergesort with a simple swap that correctly places the largest element (local maxima) and then invokes the sort function on all but this element. So on every invocation, we keep correctly placing the largest element but in a recursive manner.

A visualization of this algorithm could be found in this youtube video.

Asymptotic Analysis

The runtime of Slowsort could be computed by the following recurrence relation

slowsort recurrence relation

When the above recurrence relation is solved and we find that the asymptotic lower bound for T(n) is given by

lower bound of slowsort

The above expression suggests that lower bound of Slowsort is non-polynomial in nature and for a sufficiently large 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. The illustration below compares the time taken by Slowsort and the recursive implementation of Bubblesort.

slowsort vs recursive bubblesort

The iterative implementation of Bubblesort stood no chance in terms of time taken for smaller sets of integers, hence the chart was plotted against the recursive implementation of it. The iterative bubble sort for smaller arrays is nearly flat.

Slowsort vs Bogosort

Bogosort is a sorting algorithm that has an average case time complexity of O(n!) and an unbounded time in the worst case. The algorithm keeps on permuting (shuffling) the array till it is sorted which introduces an unboundedness in its implementation and hence the algorithm is considered to be the worst sorting algorithm ever.

The reason that we should rate Slowsort highly is the fact the Bogosort could sort the list in its first shuffle while Slowsort is deterministic and will take O(n ^ log(n)) time in best case scenario.

A rule that every algorithm follows is that every step that it takes actually makes some progress towards the final goal. Bogosort does not guarantee progress, and since it randomly shuffles the array, at one iteration we could end up at a nearly sorted array while the next shuffle takes us afar.

Slowsort is deterministic and convergent. The number of swaps made (inversions) during the execution is non-increasing which means once two items are swapped they are in the correct order relative to each other. In other words, we say that Slowsort never makes a wrong move.

References


Other articles that you might like


If you liked what you read, consider subscribing to my weekly newsletter at arpitbhayani.me/newsletter where, once a week, I write an essay about programming languages internals, or a deep dive on some super-clever algorithm, or just a few tips on building highly scalable distributed systems.

You can always find me browsing through twitter @arpit_bhayani.