Sorting algorithm using median-of-three?

Question

I am using the following algorithm, which I found on the internet and modified a little to find the median of three:

private static List<int> quicksort(List<int> arr)
{
    List<int> loe = new List<int>(), gt = new List<int>();

    if (arr.Count < 2)
        return arr;

    int middle = arr.Count / 2;
    int left = arr.First();
    int right = arr.Last();
    int MoT = 0;

    if (middle < left && middle < right) 
        MoT = middle;
    if (left < middle && left < right) 
        MoT = left;
    if (right < left && right < middle) 
        MoT = right;

    int pivot_val = arr[MoT]; //assign median pivot
    arr.RemoveAt(MoT);

    foreach (int i in arr)
    {
        if (i <= pivot_val)
            loe.Add(i);
        else if (i > pivot_val)
            gt.Add(i);
    }

    List<int> resultSet = new List<int>();
    resultSet.AddRange(quicksort(loe));

    if (loe.Count == 0)
        loe.Add(pivot_val);
    else
        gt.Add(pivot_val);

    resultSet.AddRange(quicksort(gt));
    return resultSet;
}

It correctly sorts an array of size 10, however, it only sorts and displays 7 numbers, instead of 10 numbers. Any ideas how I can fix this?

Answer 1

You add the pivot value back into loe AFTER you have already copied loe to the result, in the case where loe was empty. This does nothing. You should replace

loe.Add(pivot_val);

with

resultSet.Add(pivot_val);

or similar.