Spoiler - sorting a list of ints in linear time

spoiler-listsort.cs

using System;

// It's a bit naive in that it performs more copies than necessary, but it's clearly linear time.
// The extra copies and other overhead can be optimized away if needed.
// [Yes, it's a naive implementation of radix sort. :)]

static void Sort(Span<uint> span)
{
    Span<uint> scratch = new uint[span.Length];

    for (int i = 0; i < 32; i++)
    {
        OrderByBitPos(span, scratch, i);
    }

    static void OrderByBitPos(Span<uint> span, Span<uint> scratch, int bitPos)
    {
        // First copy everything to scratch so that we can write
        // the ordered result back into the original span.

        span.CopyTo(scratch);

        // Forward walk - write everything that has 'bitPos' unset
        // to the front of the span.

        int spanIdx = 0;
        for (int i = 0; i < scratch.Length; i++)
        {
            if ((scratch[i] & (1 << bitPos)) == 0)
            {
                span[spanIdx++] = scratch[i];
            }
        }

        // Reverse walk - write everything that has 'bitPos' set
        // to the end of the span.

        spanIdx = span.Length - 1;
        for (int i = scratch.Length - 1; i >= 0; i--)
        {
            if ((scratch[i] & (1 << bitPos)) != 0)
            {
                span[spanIdx--] = scratch[i];
            }
        }

        // At this point, 'span' is ordered in the low (1 << bitPos) bits.
    }
}