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

private static void Merge(int[]A, int[]aux, int lo, int mid, int hi)
{
    for (int k = lo; k <= hi; k++)
        aux[k] = A[k];


    int i = lo, j = mid + 1;
    for (int k = lo; k <= hi; k++)
    {
        if      (i > mid)           A[k] = aux[j++];
        else if (j > hi)            A[k] = aux[i++];
        else if (aux[j] < aux[i])   A[k] = aux[j++];
        else                        A[k] = aux[i++];
    }
}

private static void Sort(int[] A, int[] aux, int lo, int hi)
{
    if (hi <= lo) return;
    int mid = lo + (hi - lo) / 2;
    Sort(A, aux, lo, mid);
    Sort(A, aux, mid + 1, hi);
    if (A[mid + 1] > A[mid]) return;
    Merge(A, aux, lo, mid, hi);
}

public static void Sort(int[] A)
{
    int[] aux = new int[A.Length];
    Sort(A, aux, 0, A.Length - 1);
}

Answer 2

A Simple Merge Sort Implementation.

https://github.com/bharathkumarms/AlgorithmsMadeEasy/blob/master/AlgorithmsMadeEasy/MergeSort.cs

using System;
using System.Collections.Generic;
using System.Linq;

namespace AlgorithmsMadeEasy
{
    class MergeSort
    {
        public void MergeSortMethod()
        {
            var input = System.Console.ReadLine();
            string[] sInput = input.Split(' ');
            int[] numbers = Array.ConvertAll(sInput, int.Parse);
            int len = numbers.Length;
            MergeSort_Recursive(numbers, 0, len - 1);
            for (int i = 0; i < len; i++)
            {
                Console.Write(numbers[i] + " ");
            }

            Console.ReadLine();
        }

        static public void MergeSort_Recursive(int[] numbers, int left, int right)
        {
            int mid;

            if (right > left)
            {
                mid = (right + left) / 2;
                MergeSort_Recursive(numbers, left, mid);
                MergeSort_Recursive(numbers, (mid + 1), right);

                DoMerge(numbers, left, (mid + 1), right);
            }
        }

        static public void DoMerge(int[] numbers, int left, int mid, int right)
        {
            int[] temp = new int[numbers.Length];
            int i, left_end, num_elements, tmp_pos;

            left_end = (mid - 1);
            tmp_pos = left;
            num_elements = (right - left + 1);

            while ((left <= left_end) && (mid <= right))
            {
                if (numbers[left] <= numbers[mid])
                    temp[tmp_pos++] = numbers[left++];
                else
                    temp[tmp_pos++] = numbers[mid++];
            }

            while (left <= left_end)
                temp[tmp_pos++] = numbers[left++];

            while (mid <= right)
                temp[tmp_pos++] = numbers[mid++];

            for (i = 0; i < num_elements; i++)
            {
                numbers[right] = temp[right];
                right--;
            }
        }
    }
}

/*
Sample Input:
6 5 3 2 8

Calling Code:
MergeSort ms = new MergeSort();
ms.MergeSortMethod();
*/

Answer 3

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 .