Another Quicksort stackoverflow

Question

So I've been trying to implement a quicksort myself, just to learn something from it, but it also generates a stackoverflowexception, but I can't seem to find what the cause is.

Can someone give me a clue?

  public void Partition(List<int> valuelist, out List<int> greater, out List<int> lesser)
        {
            lesser = new List<int>();  // <-- Stackoverflow exception here!
            greater = new List<int>();

            if (valuelist.Count <= 1)
                return;

            pivot = valuelist.First();

            foreach (int Element in valuelist)
            {
                if (Element <= pivot)
                    lesser.Add(Element);
                else
                    greater.Add(Element);
            }
        }

        public List<int> DoQuickSort(List<int> list)
        {
            List<int> great;
            List<int> less;

            Partition(list, out great, out less);

            DoQuickSort(great);
            DoQuickSort(less);

            list.Clear();
            list = (List<int>)less.Concat(great);

            return list;

        }

Answer 1

You're not putting any conditions on your recursive calls to DoQuicksort, so it'll never stop recursing, leading to a stack overflow. You should only be calling DoQuicksort on a list if it contains more than one element.

Edit: As Will said in his comment, this is a very slow approach to "Quicksort". You should look at in-place partitioning algorithms, as mentioned on Wikipedia's Quicksort article.

Answer 2

you are doing an infinite loop right there

  DoQuickSort(great);

you need a way to get out of that loop with a flag or a condition

Edit
I will add that in debugging mode, with default setting, you can only reach between 10,000 and 16,000 recursive call before an exception is thrown and between 50,000 and 80,000 when in release mode, all depend on the actual code executed.

If you play with a huge number of values, you might need to manage yourself that recursive call by using a Stack object.

sample code to see how much call before it crash;
(debug; 14,210 call, release 80,071 call)

   static int s = 1;
    static void Main(string[] args)
    {
        o();
    }

    static void o()
    {
        s++;
        Console.WriteLine(s.ToString());
        o();
    }

Answer 3

I think one of the problems in your code that you keep the pivot value when partitioning the list. This means that you will run into a situation where all values partition into either greater or less, and the partitioning will stop working. This will effectively not letting you split one of the lists anylonger, so the exit condition in the Partition method is never satisfied.

You should select a pivot value, remove the pivot element from the list (this part is missing in your code), parition it in greater and less lists, sort those (recursively), and then concatenate the less list, the pivot element (this is also, naturally, missing in your code) and the greater list.

I can post an updated, working, code sample, but since you are in "learning mode", I will keep it to myself until you ask for it :)