No PDF plugin is installed for this browser. Click here to download the PDF.

Sorting the Slow Way: An Analysis of Perversely Awful Randomized Sorting Algorithms

Abstract. This paper is devoted to the “Discovery of Slowness.” The
archetypical perversely awful algorithm bogo-sort, which is sometimes
referred to as Monkey-sort, is analyzed with elementary methods. More-
over, practical experiments are performed.

To our knowledge, the analysis of perversely awful algorithms can be tracked
back at least to the seminal paper on pessimal algorithm design in 1984 [2]. But
what’s a perversely awful algorithm? In the “The New Hacker’s Dictionary” [7]
one finds the following entry:

bogo-sort: /boh‘goh-sort’/ /n./ (var. ‘stupid-sort’) The archetypical perversely
awful algorithm (as opposed to © bubble sort, which is merely the generic
*bad* algorithm). Bogo-sort is equivalent to repeatedly throwing a deck of
cards in the air, picking them up at random, and then testing whether they
are in order. It serves as a sort of canonical example of awfulness. Looking at a
program and seeing a dumb algorithm, one might say ”Oh, I see, this program
uses bogo-sort.” Compare © bogus, © brute force, © Lasherism.

Among other solutions, the formerly mentioned work contains a remarkably slow
sorting algorithm named slowsort achieving running time Ω nlog n/(2+ǫ) even
in the best case. But the running time, still being sub-exponential, does not
improve (i.e., increase) in the average case, and not even in the worst case. On
the contrary, the analysis of bogo-sort carried out here shows that this algo-
rithm, while having best-case expected running time as low as O(n), achieves
an asymptotic expected running time as high as Ω(n · n!) already in the average
case. The pseudo code of bogo-sort reads as follows:

Algorithm 1 Bogo-sort
1: Input array a[1 . . . n]
2: while a[1 . . . n] is not sorted do
 randomly permute a[1 . . . n]
4: end while

The test whether the array is sorted as well as the permutation of the array
have to be programmed with some care:

1: procedure
 sorted: {returns
true if the array is sorted and
false otherwise}
 for i = 1 to n − 1 do
 if a[i] > a[i + 1] then
 return false
 end if
 end for
 return true
 end procedure
1: procedure randomly permute:
{permutes the array}
2: for i = 1 to n − 1 do
 j := rand[i . . . n]
 swap a[i] and a[j]
5: end for
6: end procedure

The second algorithm is found, e.g., in [5, p.139]. Hence the random permu-
tation is done quickly by a single loop, where rand gives a random value in the
specified range. And the test for sortedness is carried out from left and right.
In this work we present a detailed analysis, including the exact determination
of the expected number of comparisons and swaps in the best, worst and average
case. Although there are some subtleties in the analysis, our proofs require only a
basic knowledge of probability and can be readily understood by non-specialists.
This makes the analysis well-suited to be included as motivating example in
courses on randomized algorithms. Admittedly, this example does not motivate
coursework on efficient randomized algorithms. But the techniques used in our
analysis cover a wide range of mathematical tools as contained in textbooks such
as [4].
We will analyze the expected running time for bogo-sort under the usual
assumption that we are given an array x = x 1 x2 . . . xn containing a permutation
of the set of numbers {1, 2, . . . , n}. In a more abstract fashion, we are given a
list containing all elements of a finite set S with |S| = n and an irreflexive,
transitive and antisymmetric relation ⊏. To analyze the running time of the
algorithm, which is a comparison-based sorting algorithm, we follow the usual
convention of counting on one hand the number of comparisons, and on the other
hand the number of swaps. An immediate observation is that the algorithm isn’t
guaranteed to terminate at all. However, as we will prove that the expectation
of the running time T is finite, we see by Markov’s inequality
that the probability of this event equals 0. There are essentially two different
initial configurations: Either the list x is initially sorted, or it is not sorted. We
have to make this distinction as the algorithm is smart enough to detect if the
given list is initially sorted, and has much better running time in this case. This
nice built-in feature also makes the running time analysis in this case very easy:
The number of total comparisons equals n − 1, and the total number of swaps
equals zero, since the while-loop is never entered.
We come to the case where the array is not initially sorted. Note that the
first shuffle yields a randomly ordered list, so the behavior of the algorithm does
no longer depend on the initial order; but the number of comparisons before the
first shuffle depends on the structure of the original input.