Abstract
How it all started by Richard Harter
Other sorts by various
A convergence proof by Richard Harter and Thomas Marlowe
Inefficient sorts and complexity by Thomas Marlowe
Some remarks on complexity of three other pessimal sorting algorithms by Thomas Marlowe
Another evil sort by Carl Howells
Acknowledgements

Abstract

This paper is the condensation of a discussion of inefficient sorts in the talk.origins newsgroup. The main focus was on a sort suggested by Richard Harter. Although the topic (and much of the discussion) was apparently frivolous it raised real mathematical issues which were considered in some depth by Thomas Marlowe.

How it all started

In the talk.origins newsgroup someone made an offhand remark that they didn’t see how anybody, no matter how klutzy their programming, could write an O(n^3) sort. I immediately gave a simple example:

	begin procedure sort(a,n)
		begin do i = 1...n
			bubblesort(a,i)
		end do
	end procedure sort

I then casually mentioned my favorite inefficient sort:

	begin procedure sort(a,n)
		begin loop
			if (sorted(a,n)) return
			i = random(n)
			j = random(n)
			if (i .gt. j) swap(i,j)
			if (a(i) .gt. a(j)) swap(a(i),a(j))
		end loop
	end procedure sort

This bit of programming fluff produced a great deal of response; evidently there is something deliciously perverse about deliberate inefficiency. For example there was the following exchange:

Richard Harter:
It is immoral to write bad code even if it is never going to be used.

Wade Hines:
Does this apply to didactics about inefficient sorts?

Stephen F. Schaffner
Just because it’s immoral doesn’t mean you shouldn’t do it.

Richard Harter:
It’s an original sin thingie. Before Adam used [1] the apple he wrote perfect code. When Eve listened to the serpent [2] and talked Adam into using the apple [3] they lost their user account and the ability to write perfect code.

[1] The sacred accounts refer to eating the apple but this is a bit of confusion which arose because the AI program in THE APPLE would say “EAT ME” when it was not pleased with its input.

[2] The identity of the serpent is obscure. It is rumored that he is currently running a computer company in Redmond.

[3] Eve was tempted by designer colors.

{ || i : 0 <= i < N : A[i],A[i+1] := A[i+1],A[i]  if A[i] > A[i+1] }

Mark VandeWettering accidently simplified my algorithm to get the monkeysort (random swap) algorithm: keep randomly swapping element pairs until the array is sorted. Wade Hines correctly identified Mark’s algorithm as the monkeysort algorithm. See the analysis below by Thomas Marlowe for a discussion of the performance of this algorithm.

Thomas Marlowe mentioned several sorts which are even worse:

An algorithm which checks all permutations to see if that rearrangement is correct clearly has WC O (N * N!) running time.

An algorithm which guesses a random permutation and checks has average case complexity O (N * N!), since the chance of guessing the right permutation is 1/N!.

[note: O(N * N!) does not equal O(N!)]

You can add another factor of N to most algorithms by insisting on checking every pair of indices. If you check in lexical order, you cannot conclude until you check the last pair that you really have a sorted list.

/*
 * The time complexity of this thing is O(n^(a log n))
 * for some constant a. This is a multiply and surrender
 * algorithm: one that continues multiplying subproblems
 * as long as possible until their solution can no longer
 * be postponed.
 */
void sillysort(int a[], int i, int j){
        int t, m;
        for(;i!=j;--j){
                m=(i+j)/2;
                sillysort(a, i, m);
                sillysort(a, m+1, j);
                if(a[m]>a[j]){ t=a[m]; a[m]=a[j]; a[j]=t; }
        }
}

Several people mentioned improbable sorts based on analogues with evolution. And finally I mentioned another sort which remains unanalyzed but whose performance is abysmal:

The idea is to give each value a ranking so that the big values have a high ranking and the small ones a low ranking. We then group the values of equal rank and reorder the list so that the groups are in order.

The assignment of ranks is done as follows: The initial value in the list is given a rank of 0. We step through the list. If the current value being looked at is greater than the previous value it is given a rank of one more than the rank of the previous value and, if less, it is given a rank of one less than the rank of the previous value. Here is an example of the ranking and reordering:

old list: 1, 8, 3, 4, 5, 6, 7, 2, 9
ranking:  0, 1, 0, 1, 2, 3, 4, 3, 4
new list: 1, 3, 8, 4, 5, 6, 2, 7, 9

Suppose that we have a state S and a metric on S, m(S) .GE. 0, and a suite of operations on S, f0…fn, and we want to apply operations on S sequentially until m(S) = 0. Our code looks something like this:

	begin loop
		select f such that m(f(S)) .LT. m(S)
		if no f selected escape loop
		S <- f(S)
	end loop

Now this loop must terminate (on a computer – if m(S) is a value on the reals it could approach a limit point) because m(S) cannot be reduced indefinitely. It will produce the desired result (m(S)=0) if it is the case that whenever m(S) > 0 there is an f such that m(f(S)) < m(S).

The key measure of the out-of-sorts (sorry!) of a list is the number of inversions: the cardinality of the set of all pairs (i,j) with i < j and A[i] > A [j]. (For simplicity, assume all elements are distinct.) Clearly, any list with zero inversions is sorted.

Any algorithm which

1. Never increases the number of inversions (as measured at the end of a bounded-length computation step) and
2. Has a probability bounded away from 0 of detecting and eliminating an inversion if one exists [it’s sufficient that some fixed length sequence has this property, which is the case with most deterministic algorithms], and
3. Has a probability bounded away from 0 of detecting that no inversions exist and terminating

This provides a sharper bound on the average complexity of the sorting algorithm of the form:

	while (not sorted) do {
		generate a random pair (I,J);
		if (I >= J) continue;
		if the pair corresponds to an inversion {
			swap;
			test and return if sorted; }
	}

NUMBER OF TRIALS

In the worst case (a reverse sorted list) there are N * (N-1)/2 inversions.

With K inversions, any given pair (I,J) has a probability K / N^2 of corresponding to one of them, so an inversion can be expected after N^2 / K trials, and the result decreases the number of inversions by at least 1, and by exactly 1 if I and J are adjacent.

Thus a bound for the total number of trials is

	SUM_{r=1}^{N*(N-1)/2} N^2/R 
		= N^2 SUM_{r=1}^{N*(N-1)/2} 1/R 
		~ N^2 ln (N^2) = O (N^2 lg N)

Since each swap can lower the number of inversions by at most N, this is also a lower bound on the expected number of trials in the worst case.

Finally, since the average number of inversions is N * (N-1)/4 (just pair sequences with their reverses), this is in fact also an average bound for random sequences.

COMPLEXITY

The actual average-case complexity is C * T, where C is the expected number of trials, and T is the cost per trial.

In the naive algorithm, the cost of testing for an inversion and swapping is constant (O (1)), while the cost of testing is O (N), giving a total complexity of O (N^3 lg N).

It has already been suggested that we can add a factor of N by checking all N * (N-1)/2 pairs, for O (N^4 lg N). While we could check all N^2 pairs, this would not only result in redundant information, but redundant items of information, and so is probably not credible — and in any case only buys a constant factor increase in time.

GETTING REALLY UGLY

We can actually do worse, by again generating random pairs and maintaining a bitvector (this time of length N^2, for simplicity of coding). The neat thing here is that we get a third layer of looping, since we keep having to check the bitvector array to see that it is identically 1.

	while (not sorted) do {
		generate a random pair (I, J);
		if (I >= J) continue;
		if the pair corresponds to an inversion {
			swap;
			checked = 0;
			while (not checked) do {
				generate a random pair (S, T);
				check if (A[S], A{T}) in correct order;
				on failure break; /* exit to outer loop */
				/* at this point. may be sorted */
				/*	and may be finished checking */
				checked [S,T] = 1;
				tested = 1;
				for (X,Y) = (1,1) to (N,N) do {
					tested = tested * Check [X,Y];
				}
				checked = tested;
			}
		}
	}

Thus the total average-case complexity is

	O (N^6 (lg N)^2)

	O (N! * N^4 * (lg N)^2) = O(N!)

IMPROVING A BAD ALGORITHM

As mentioned in earlier, any monotone algorithm with an expensive termination test can be made faster by simply not always testing. Let the expected number of steps be S, the test cost T, and the generating cost G. The total expected cost is

	O (S * (T + G))

If T >> G, and S >> T/G, tests are made only every T/G steps. The amortized cost of testing is constant. Note that up to T/G additional steps may be required. The (average-case) complexity is then

	O ((S + T/G) * (G + 1/(T/G) * T) = O (S * G)

	O ((S + S) * (G + 1/S * T)) = O (S * max (G, T/S)) 
		= O (max (S * G, T))

	O (N^2 lg N) for either the O (N) or O (N^2) test
	O (N^4 lg N) for the N^4 lg N testing method.

1. Random swap algorithm

In principle, the expected number of steps starting with a worst-case (reverse sorted) list can be found by looking at the Markov process with N! states (one per permutation).

• The identity permutation is absorbing, since the algorithm terminates. Every other permutation has N*(N-1)/2 + 1 successors: N*(N-1)/2 successors resulting from applying a single transposition (swap), with probability 2/N^2 (since the indices could be generated in either order), and a self-loop resulting from choosing [I,I], with probability 1/N.
• Any permutation not a single swap from the identity has N*(N-1)/2 incoming edges, as does the identity permutation; the others have one fewer incoming edge, since the identity is absorbing.

2. Reversing subsequence algorithm

Roy Thearle made the following suggestion:

BTW, have you considered that instead of just swapping the two randomly chosen locations if they’re out of order, you could invert the whole sequence of items between them (inclusive)?

I think this would not only increase the time required for each swap, but also make the sort less efficient due to reducing the tendency for low items to drift downwards and high items to drift upwards.

Rather, it is monotonic in the following sense, which is probably a key to a more careful analysis (not presented here, my brain isn’t up to it): Any operation results in a sequence which is earlier in lexicographic order, and later in reverse lexicographic order, than the original. (The subsequence before the reversal remains the same, and the first element in the reversal becomes smaller. Likewise, the subsequence afterwards remains the same, and the last reversed element becomes larger.)

It is also true that (*) if there is a partition point K (think quicksort) so that all entries before position K are smaller, and all entries after are larger, the algorithm cannot undo that. In particular, once the smallest element gets to be first, or the largest last, they will never move.

Thus the number of steps for the algorithm can be bounded by iterating the number of steps it takes to move one of the extreme elements to the end (necessarily the correct end) of the list. Out of N^2 pairs, there are 4 that will do the right job — [1,L], [L,1], {H,N], {N,H], where L and H are the indices of the minimal and maximal elements, respectively. The expected number of steps is thus

 
       Steps (N) <= N^2/4 + Steps (N-1)

Total number of steps <= O (N^3). (As compared to O (N^2 lg N) for the swap variant.)

I suspect, but haven’t yet shown, that there is a much smaller chance of forming any other partition point, and that this won’t reduce the expected value by more than a constant. Simulation might be the way to go here.

AN ARGUMENT FOR A LOWER COMPLEXITY

There is, surprisingly, a heuristic argument for an O (N^2 lg N) complexity for this variant as well. Consider the set of all permutations, and the action of individual transpositions using the random swap and random reverse algorithms. Then

• Each permutation is either stable for both algorithms for a given proposed transposition (because there is no inversion there), or results in an operation.
• Exactly half of all permutations are stable for a given pair, and only the identity is stable for all pairs.
• Each permutation will be changed by exactly as many pairs as it has inversions (essentially by definition of inversion and of the two algorithms.)