Quick Sort Algorithm - Median of Three

Question

I have the following quicksort algorithm which uses the leftmost as a pivot which is working perfectly well:

public static void QuickSortLeft(int[] array, int start, int end)
{
    int left = start;
    int right = end;

    int pivot = array[start];

    while (left <= right)
    {
        while (array[left] < pivot)
        {
            left++;
        }

        while (array[right] > pivot)
        {
            right--;
        }

        if (left <= right)
        {
            swap(array,left, right);

            left++;
            right--;
        }
    }

    // Recursive calls
    if (start < right)
    {
        QuickSortLeft(array, start, right);
    }

    if (left < end)
    {
        QuickSortLeft(array, left, end);
    }
}

Now I tried to do the Median of Three optimisation on the above my taking the median of the first, last and middle position and use the median as pivot as below, however I am getting a StackOverflow exception

public static void QuickSortMedian(int[] array, int start, int end)
{
    int left = start;
    int right = end;

    int pivot = (array[start] + array[(start + (end - start)) / 2] + array[end]) / 2;

    while (left <= right)
    {
        while (array[left] < pivot)
        {
            left++;
        }

        while (array[right] > pivot)
        {
            right--;
        }

        if (left <= right)
        {
            swap(array, left, right);

            left++;
            right--;
        }
    }

    // Recursive calls
    if (start < right)
    {
        QuickSortMedian(array, start, right);
    }

    if (left < end)
    {
        QuickSortMedian(array, left, end);
    }
}

Answer 1

You're calculating the average (but incorrectly - it should be /3, not /2), not the median.

You should pick the middle element of the three.

Something like: (pseudo-code)

sort(left, mid, right)
pick mid

With your current code, it's likely to end up with a value larger than everything else, so you can possibly end up partitioning off 0 elements to the right, just recursing on the same data towards the left repeatedly.

Answer 2

This will give you the median:

public static class Extensions
{
    public static T Median<T>(this IEnumerable<T> source) where T:IComparable<T>
    {
        if (source == null)
        {
            throw new ArgumentException("source");
        }
        var sortedValues = source.OrderBy(v => v).ToList();
        if (sortedValues.Count == 0)
        {
            throw new InvalidOperationException("Sequence contains no elements");
        }
        var midpoint = (sortedValues.Count/2);
        return sortedValues[midpoint];
    }
}