Sorting algorithms

Lets talk about them! Which ones do you like/use/have implemented/have invented/etc.?

Code related:

    // A spectacular variant of bogo-sort which has the interesting property
    // that, if the Many Worlds interpretation of quantum mechanics is true, it
    // can sort an arbitrarily large array in linear time.
    static BogoSort(arrayToSort : array [int]) : void
    {
        // permute the array randomly using a quantum process
        def rnd = Random(DateTime.Now.Millisecond);
        def sort(left = 0)
        {
            when (left < arrayToSort.Length - 1)
            {
                def right = rnd.Next(left, arrayToSort.Length);
                def tmp = arrayToSort[left];
                arrayToSort[left] = arrayToSort[right];
                arrayToSort[right] = tmp;
                sort(left + 1);
            }
        }
        sort();

        // check if array is sorted
        def check(left = 0)
        {
            def right = left + 1;
            when (right < arrayToSort.Length)
            {
                if (arrayToSort[left] < arrayToSort[right])
                    check(right);
                else
                    throw Exception("Sort failed! Please destroy the universe. :(");
            }
        }
        check();
    }

My current favourite is the radix sort variant where you count the number of items that go in each bucket in the preceding radix pass, and therefore can produce your intermediate outputs right off the bat without linked lists or other such structures that require dynamic allocation. Destructive radixsort ends up using N temporary space for N sorted keys (plus a small constant amount depending on how big your radix is), which isn't that big a deal given that just storing the data you're about to sort requires about as much too.

Not exactly the most exciting algorithm around, and rather shitty from a theoretical standpoint. However, in today's computers optimization is about hitting the cache as often as possible and avoiding impredictable branching; this kind of radix sorting accomplishes the former by allocating temporary memory at the start of the routine and by not doing dynamic memory management, and the latter by using bitwise operations and indexing rather than comparisons. The "N storage to sort N items" issue's cache effect can be mitigated with prefetch instructions, as every pass of radix sort fetches keys in order. (Plus the temp space can be allocated on the stack if sufficiently small, which is nearly guaranteed to be "hot" already.)

Radixsort also has the worst-case advantage over qsort, which is nice if you're sorting inputs from an untrusted source, i.e. no chance of exploitable worst-case performance.