idm

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?