Quicksort Without Recursion Am teaching myself about sorting techniques and trying my hand at a quicksort implementation. I found a lot of examples based on recursion but didn't want to go that route in a language that doesn't support tail-call optimization.

public static class ListExtensions
{
    public static void InsertionSort&lt;T&gt;(this IList&lt;T&gt; values, int startIndex, int endIndex, IComparer&lt;T&gt; comparer) {
        var left = startIndex;
        var right = 0;
        var temp = default(T);

        while (left &lt; endIndex) {
            right = left;
            temp = values[++left];

            while ((right &gt;= startIndex) &amp;&amp; (0 &lt; comparer.Compare(values[right], temp))) {
                values[(right + 1)] = values[right--];
            }

            values[(right + 1)] = temp;
        }
    }
    public static void InsertionSort&lt;T&gt;(this IList&lt;T&gt; values, IComparer&lt;T&gt; comparer) {
        InsertionSort(values, 0, (values.Count - 1), comparer);
    }
    public static void InsertionSort&lt;T&gt;(this IList&lt;T&gt; values) {
        InsertionSort(values, Comparer&lt;T&gt;.Default);
    }
    public static void QuickSort&lt;T&gt;(this IList&lt;T&gt; values, int startIndex, int endIndex, IComparer&lt;T&gt; comparer, IRandomNumberGenerator randomNumberGenerator) {
        var range = (startIndex, endIndex);
        var stack = new Stack&lt;(int, int)&gt;();

        do {
            startIndex = range.startIndex;
            endIndex = range.endIndex;

            if ((endIndex - startIndex + 1) &lt; 31) {
                values.InsertionSort(startIndex, endIndex, comparer);

                continue;
            }

            var pivot = values.SampleMedian(startIndex, endIndex, comparer, randomNumberGenerator);
            var left = startIndex;
            var right = endIndex;

            while (left &lt;= right) {
                while (0 &gt; comparer.Compare(values[left], pivot)) { left++; }
                while (0 &gt; comparer.Compare(pivot, values[right])) { right--; }

                if (left &lt;= right) {
                    values.Swap(left++, right--);
                }
            }

            if (startIndex &lt; right) {
                stack.Push((startIndex, right));
            }

            if (left &lt; endIndex) {
                stack.Push((left, endIndex));
            }
        }
        while (stack.TryPop(out range));
    }
    public static void QuickSort&lt;T&gt;(this IList&lt;T&gt; values, IComparer&lt;T&gt; comparer, IRandomNumberGenerator randomNumberGenerator) {
        QuickSort(values, 0, (values.Count - 1), comparer, randomNumberGenerator);
    }
    public static void QuickSort&lt;T&gt;(this IList&lt;T&gt; values) {
        QuickSort(values, Comparer&lt;T&gt;.Default, FastRandom.Default);
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    private static T SampleMedian&lt;T&gt;(this IList&lt;T&gt; values, int startIndex, int endIndex, IComparer&lt;T&gt; comparer, IRandomNumberGenerator randomNumberGenerator) {
        var left = randomNumberGenerator.NextInt32(startIndex, endIndex);
        var middle = randomNumberGenerator.NextInt32(startIndex, endIndex);
        var right = randomNumberGenerator.NextInt32(startIndex, endIndex);

        if (0 &gt; comparer.Compare(values[right], values[left])) {
            Swap(values, right, left);
        }

        if (0 &gt; comparer.Compare(values[middle], values[left])) {
            Swap(values, middle, left);
        }

        if (0 &gt; comparer.Compare(values[right], values[middle])) {
            Swap(values, right, middle);
        }

        return values[middle];
    }
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    private static void Swap&lt;T&gt;(this IList&lt;T&gt; values, int xIndex, int yIndex) {
        var temp = values[xIndex];

        values[xIndex] = values[yIndex];
        values[yIndex] = temp;
    }
}
All in all there is not much to comment. I like the iterative mechanism with the stack. Trying other collections (linked list, dictionary, hashset etc.) doesn't seem to improve the performance.

One could argue that it would be nice to have the partition part in a dedicated function to improve readability, but again the algorithm isn't that hard to understand.

The really improvement of performance comes from the use of InsertionSort() when the range is smaller than 31 - and that magic number seems to be the right limit. And Insertion Sort seems to be the right choice over other simple algorithms like Selection Sort.

The performance gain from SampleMedian() is little or absent for smaller data sets, but is significant for larger (> 10000) - compared to let it return values[startIndex] or values[startIndex + (endIndex - startIndex) / 2].

All in all a well designed algorithm optimized in respect to performance.



A minor thing in SampleMedian():

I don't like:

if (0 &gt; comparer.Compare(values[right], values[left]))


but rather: 

if (comparer.Compare(values[right], values[left]) &lt; 0)


but that's a matter of habit.



Of course you should check if the arguments are valid (values != null, startIndex &lt; endIndex etc.)