IComparable<T> gives stackoverflow when used for negative numbers?

Question

This is a weired problem, I have implemented simple quick sort as follows..

        static void Main(string[] args)
    {
        List<int> unsorted = new List<int> { 1, 3, 5, 7, 9, 8, 6, 4, 2 };
        List<int> sorted = quicksort(unsorted);
        Console.WriteLine(string.Join(",", sorted));
        Console.ReadKey();
    }

    private static List<T> quicksort<T>(List<T> arr) where T : IComparable<T>
    {
        List<T> loe = new List<T>(), gt = new List<T>();

        if (arr.Count < 2)
            return arr;

        int pivot = arr.Count / 2;
        T pivot_val = arr[pivot];
        arr.RemoveAt(pivot);

        foreach (T i in arr)
        {
            if (i.CompareTo(pivot_val) <= 0)
                loe.Add(i);
            else
                gt.Add(i);
        }

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

        gt.Add(pivot_val);

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

Output is : 1,2,3,4,5,6,7,8,9

But When I use any negative number in the unsorted list there is a stackoverflow error,

for example if List unsorted = new List { 1, 3, 5, 7, 9, 8, 6, 4, 2, -1 }; Now there is a stackoverflow..

What's going on? Why this is not working ?

Answer 1

Your algorithm has a bug. Consider the simplest input list { 1, -1 }. Let's step through your logic.

1. You first choose a pivot index, Count / 2, which is 1.
2. You then remove the pivot element at index 1 (-1) from the arr list.
3. Next you compare each remaining element in the arr list (there's just the 1 at index 0) with the pivot.
4. The 1 is greater than the pivot (-1) so you add it to the gt list.
5. Next you quicksort the loe list, which is empty. That sort returns an empty list, which you add to the result set.
6. You then add the pivot value to the end of the gt list, so the gt list now looks like this: { 1, -1 }. Notice that this is the exact same list as you started with.
7. You then attempt to quicksort the gt list. Since you are calling the quicksort routine with the same input, the same sequence of steps happens again, until the stack overflows.

It seems the error in your logic is that you blindly add the pivot to the gt list without comparing it to anything. I'll leave it to you to figure out how to make it work.

Edited to add: I'm assuming this is a homework assignment, but if it's not, I would highly recommend using .NET's built in Sort() method on List<T>. It has been highly optimized and heavily tested, and will most likely perform better than anything home-brewed. Why reinvent the wheel?

Answer 2

if you don't have a debugger try this...

foreach (T i in arr)
        {
            if (i.CompareTo(pivot_val) <= 0)
            {

                loe.Add(i);
                Console.WriteLine("loe.add " + i.ToString());
            }
            else
            {
                gt.Add(i);
                Console.WriteLine("gt.add " + i.ToString());
            }
        }