A simple Merge Sort implementation using C#.

public static void MergeSort(int[] input, int left, int right)
{
if (left < right)
{
int middle = (left + right) / 2;
MergeSort(input, left, middle);
MergeSort(input, middle + 1, right);
//Merge
int[] leftArray = new int[middle - left + 1];
int[] rightArray = new int[right - middle];
Array.Copy(input, left, leftArray, 0, middle - left + 1);
Array.Copy(input, middle + 1, rightArray, 0, right - middle);
int i = 0;
int j = 0;
for (int k = left; k < right + 1; k++)
{
if (i == leftArray.Length)
{
input[k] = rightArray[j];
j++;
}
else if (j == rightArray.Length)
{
input[k] = leftArray[i];
i++;
}
else if (leftArray[i] <= rightArray[j])
{
input[k] = leftArray[i];
i++;
}
else
{
input[k] = rightArray[j];
j++;
}
}
}
}

### Like this:

Like Loading...

*Related*

Andrei

September 10, 2013 at 12:47 AM

Thanks

Jonnie

October 1, 2014 at 11:11 PM

I am a struggling C# programming student. This is the simplest implementation of MergeSort I have found, but I am still having trouble understanding how it works exactly. Could you help me in understanding what the method is doing?

begeeben

October 10, 2014 at 12:28 AM

Hope you’d understood the idea by now. I should have named the arguments clearer and added some comments.

‘left’ is the leftmost index of the array, ‘right’ is the rightmost index.

The whole idea is to divide an array into 2 recursively until it’s down to one or two elements. Then you compare them, put them into a 2 elements array in sorted order and compare it again with another sorted 2 elements array. Doing the comparison all the way to the top until you have the original array sorted.

ex:

1. [4, 2, 7, 5, 1, 8, 9, 6, 3]

2. [4, 2, 7, 5] [1, 8, 9, 6, 3]

3. [4, 2] [7, 5]

4. [4] [2]

5. [2, 4]

6. [2, 4] [7] [5]

7. [2, 4] [5, 7]

8. [2, 4, 5, 7]

and so on…