Tell me more ×
Stack Overflow is a question and answer site for professional and enthusiast programmers. It's 100% free, no registration required.
up vote -2 down vote favorite

I tried to implement a merge sort in C# and for some reason it gives me a stackoverflow exeption,I have no idea where it comes from. The error is something small i'm guessing but i can't find it

using System;

class MergeSort
{
   public static int maxN = 60;

    public static void merge(ref int[] array, int left, int mid, int right)
    {
        int i, j;

        int[] aux = new int[maxN];
        for (i = mid + 1; i > left; i--) aux[i - 1] = array[i - 1];
        {
            for (j = mid; j < right; j++) aux[right + mid - j] = array[j + 1];
            {
                for (int k = left; k <= right; k++)
                {
                    if (aux[j] < aux[i])
                    {
                        array[k] = aux[j--];
                    }
                    else
                    {
                        array[k] = aux[i++];
                    }
                }
            }
        }
    }

    public static void mergeSort(ref int[] array, int l, int r)
      {
          if (l < r)
          {
              int m = l + ((r + l) / 2);

              mergeSort(ref array, l, m);
              mergeSort(ref array, m + 1, r);
              merge(ref array, l, m, r);
          }
          else
              return;
      }


    static void Main()
    {
        int[] nArray = new int[] { 1, 5, 14, 2, 28, 3, 90, 43, 1, 54, 43, 52 };

        Console.WriteLine("Unsorted Array : ");
        Console.Write('{');
        for (int i = 0; i < nArray.Length; i++)
        {
            Console.Write("{0}", nArray[i]);

            if(i != nArray.Length - 1) 
                Console.Write(','); 
            else 
                Console.WriteLine('}');
        }

        mergeSort(ref nArray, 0, nArray.Length);

        Console.WriteLine("Sorted array :");
        Console.Write('{');
        for (int i = 0; i < nArray.Length; i++)
        {
            Console.Write("{0}", nArray[i]);

            if (i != nArray.Length - 1)
                Console.Write(',');
            else
                Console.WriteLine('}');
        }
    }
}
share|improve this question
3  
Debug it till it starts increasing the callstack recursively. – leppie 15 hours ago
2  
I recommend you put a breakpoint in your mergeSort method on the line mergeSort(ref array, l, m); and see what your l, r and m values are. I'm sure the StackOverflowException is because l < r is never false. – Nolonar 15 hours ago
2  
Debug it? l < r is always true or (2 < 5). l is never increased. – DGibbs 15 hours ago

1 Answer

up vote 5 down vote accepted

First of all, you code doesn't work when you have just 2 elements in array. There is exception here:

for (j = mid; j < right; j++) aux[right + mid - j] = array[j + 1];

Index was outside the bounds of the array.

Second, when you pass this variables:

l = 2 r = 5

to this method:

        public static void mergeSort(ref int[] array, int l, int r)
        {
            if (l < r)
            {
                int m = l + ((r + l) / 2);

                mergeSort(ref array, l, m);
                mergeSort(ref array, m + 1, r);
                merge(ref array, l, m, r);
            }
            else
                return;
        }

you can see, that:

1. l < r
2. m = l + ((r + l) / 2) = 2 + (5 + 2) / 2 = 5
3. mergeSort(ref array, 2, 5)

Here you have recursion (enought int[] nArray = new int[] { 1, 5, 14 }; to see it).

Edit: Maybe it could help you: http://www.cs.nyu.edu/~vs667/articles/mergesort/

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.