MergeSort Implementation in C#

Question

Currently studying algorithm analysis, and instead of blindly running off of pseudo-code from my textbook, I'm implementing each algorithm in C#. This is the psuedo-code:

MERGE-SORT(A,p,r)
1  if p < r
2     q = (p+r)/2
3     MERGE-SORT(A,p,q)
4     MERGE-SORT(A,q+1,r)
5     MERGE(A,p,q,r)

MERGE(A,p,q,r)
1  n1 = q - p + 1
2  n2 = r - q
3  let L[1..n1+1] and R[1..n2+1] be new arrays
4  for i = 1 to n1
5     L[i] = A[p+i-1]
6  for j = 1 to n2
7     R[j] = A[q+j]
8  L[n1+1] = INF
9  R[n1+1] = INF
10 i = 1
11 j = 1
12 for k = p to r
13    if L[i] <= R[j]
14       A[k] = L[i]
15       i = i + 1
16    else
17       A[k] = R[j]
18       j = j + 1

This is my code:

static void Main(string[] args)
{
    int[] unsortedArray = new int[] { 5, 2, 7, 4, 1, 6, 8, 3, 9, 10 };
    MergeSort(ref unsortedArray, 1, unsortedArray.Length);
    foreach (int element in unsortedArray)
    {
        Console.WriteLine(element);
    }
    Console.Read();
}

private static void MergeSort(ref int[] unsortedArray, int leftIndex, int rightIndex)
{
    if (leftIndex < rightIndex)
    {
        int middleIndex = (leftIndex + rightIndex) / 2;
        //Sort left (will call Merge to produce a fully sorted left array)
        MergeSort(ref unsortedArray, leftIndex, middleIndex);
        //Sort right (will call Merge to produce a fully sorted right array)
        MergeSort(ref unsortedArray, middleIndex + 1, rightIndex);
        //Merge the sorted left & right to finish off.
        Merge(ref unsortedArray, leftIndex, middleIndex, rightIndex);
    }
}

private static void Merge(ref int[] unsortedArray, int leftIndex, int middleIndex, int rightIndex)
{
    int lengthLeft = middleIndex - leftIndex + 1;
    int lengthRight = rightIndex - middleIndex;
    int[] leftArray = new int[lengthLeft + 1];
    int[] rightArray = new int[lengthRight + 1];
    for (int i = 0; i < lengthLeft; i++)
    {
        leftArray[i] = unsortedArray[leftIndex + i - 1];
    }
    for (int j = 0; j < lengthRight; j++)
    {
        rightArray[j] = unsortedArray[middleIndex + j];
    }
    leftArray[lengthLeft] = Int32.MaxValue;
    rightArray[lengthRight] = Int32.MaxValue;
    int iIndex = 0;
    int jIndex = 0;
    for (int k = leftIndex; k < rightIndex; k++)
    {
        if (leftArray[iIndex] <= rightArray[jIndex])
        {
            unsortedArray[k] = leftArray[iIndex];
            iIndex++;
        }
        else
        {
            unsortedArray[k] = rightArray[jIndex];
            jIndex++;
        }
    }
}

I'm not sure where I'm messing things up -- I tried to follow the pseudo-code as well as I could, but my output is funky (i.e. repeated values and not properly sorted).

Debugging this didn't help me figure out the problem either (recursive solutions get too messy).

Where am I going wrong, and how do I fix it?

Answer 1

As correctly pointed out in the comments, C# array indexing is zero-based, while your pseudo code is one-based.

That being said, here's the errors:

1) Main method

MergeSort(ref unsortedArray, 1, unsortedArray.Length);

has to be changed to:

MergeSort(ref unsortedArray, 0, unsortedArray.Length - 1);

2) Merge method

leftArray[i] = unsortedArray[leftIndex + i - 1];

has to be change to:

leftArray[i] = unsortedArray[leftIndex + i];

3) Merge method

rightArray[j] = unsortedArray[middleIndex + j];

has to be change to:

rightArray[j] = unsortedArray[middleIndex + j + 1];

4) Merge method

for (int k = leftIndex; k < rightIndex; k++)

has to be change to:

for (int k = leftIndex; k <= rightIndex; k++)

BTW, the ref keyword in your code is not really necessay, since you're just modifying the values inside the array and not creating a new instance of it .