Many of the posts here and on 4chan have deconstructed the algorithm and proven that it is actually O(n^2) or O(n * lg n) when you include the work done by the operating system's scheduler.

However, here's a different perspective to look at this from: What if this were implemented on an FPGA?

Let's ignore for a moment that the number of gates needed would increase linearly with the size of the input. I'll also simplify the math by assuming that a list of n numbers contains only values in the range [0 .. n] .

Let's further assume that we're only sorting positive integers, and that each job sleeps for x clock cycles (where x in the input number). We could sort a list in O(n) time.

Digging even deeper: Quicksort performs an integer comparison followed by a branch O(n lg n) times. Even if your processor can compare two integers in one clock cycle, a branch is probably going to screw up your processor's pipelining and take quite a few clock cycles to execute. So, we're possibly looking at a significant speed increase even before we consider the difference in order of growth.

So, assuming a predefined upper bound on the number of items in a list, this just might be a great way to perform hardware-assisted sorts.

Thoughts?