idm

I posed the problem of finding the execution time of increment sort without first figuring it out myself. What folly! Here goes:

Obviously the best-case is O(n) to check all elements of a pre-sorted list, and the worst-case is O(∞), as is common among randomized algorithms. But for the average case, not only does the running time depend on the sizes and spread of the elements in mysterious ways, but it turns out that merely determining the expected number of iterations is hopelessly complicated for all but the simplest of inputs (at least, using only high-school mathematics).

So let’s look at the simplest non-trivial input, the list [1,0]. With just two elements, we’re essentially flipping a coin to decide which element to increment, repeating until the second element catches up to the first. Since we only require that the number of tails is one more than the number of heads, coin-toss sequences are isomorphic to downward paths in Pascal’s triangle from \( \binom{1}{1} \) to \( \binom{2k+1}{k+1} \) [Edit: where k is the number of heads].

The total number of paths to \( \binom{2k+1}{k+1} \) in Pascal’s triangle is, of course, exactly this binomial coefficient. However, note that valid paths must stay on the left side of the triangle until the last minute, so we’re actually interested in paths to \( \binom{2k}{k} \) in a “modified” triangle that only counts left-side paths. It’s not too hard to convince yourself that these numbers are

$$ \binom{n}{r}’ = \binom{n}{r} \frac{n – 2r + 1}{n – r + 1} $$

which can be proved via induction, after verifying the base-case identities \( \binom{n}{0}’ = 1 \) and \( \binom{2n+1}{n+1}’ = 0 \).

Now, the probability of choosing any particular path to row \(2k+1\) is \( 2^{-(2k+1)} \), and so the expected number of iterations to sort [1,0] is

$$ \sum_{k=0}^\infty \frac{ 2k+1 }{ 2^{2k+1} (k+1) } \binom{2k}{k} $$

Stirling’s super-handy approximation gives

$$ \binom{2k}{k} \sim \frac{4^k}{\sqrt{\pi k}} $$

and simplifies the expected value sum to approximately

$$ \sum_{k=0}^\infty \frac{2k+1 }{ 2(k+1)\sqrt{\pi k} } $$

Hm. This most certainly does not converge. Which means increment sort is O(∞) on average!

Well then. The astounding ineffectiveness of this algorithm is just beginning to dawn on me.

Okay, back into the fray.

Bogosort is a pretty well-known example of the type of sorting algorithm you might concoct if you had a little too much time lying around — literally: O(n·n!) on average. Connoisseurs of efficiency-challenged sorts are familiar with DangerMouse’s bogobogosort, which performs much worse. Here’s my contribution to this nascent field:

Increment sort

1. If the list is sorted, you’re done.
2. Increment a random list element.
3. Go to step 1.

Of note is the “lossyness” of this algorithm. Whereas people often talk about whether a sort is stable or unstable, this takes that one step further by being a “mutable” sort: the resulting list is not guaranteed to contain the same elements as the original.

Unlike other lossy sorting algorithms, however, the number of elements is preserved. The benefits to sorting may not be immediately obvious, but consider the multitude of image filters that alter pixels while preserving the original dimensions. I expect that increment sort will open the doors to a new age of academic research in mutable sorting algorithms.

Now, what’s the execution time?