MergeSort in C#

Posted on Posted in Algorithms, Divide and Conquer

What is it?

MergeSort is an algorithm that basically breaks a problem into its smallest possible units and solves them. Then it puts two units together and sorts them. It keeps doing this-using recursion-and building the units back up until it comes back with a fully solved (i.e. sorted) problem.

Note: The below example can be found on github.

How It Works

So we start with something like the code below. It starts the recursion off by passing the initial array and the range (left and right indices) we’d like to sort, in this case we’re telling it to sort the entire array.

int[] intArrRandom = StartMergeSort(intArrRandom, 0, intArrRandom.Length - 1);

Once that’s done then we have to split and sort the problem again. So to split something, we need to find the middle, right? Now at this point we need to remember that the function we call above, StartMergeSort, is going to be getting called, a lot. Well to figure out the middle, we probably need the range, so let’s calculate the range.

Now oftentimes we’ll see the range calculated as (L+R)/2 (that is the left index, plus the right index, all divided by two). The reason it’s addition, and not subtraction like we always saw in grade school, is because while you want the difference between the two numbers just remember we’re using this to find a midpoint. So if we’re going from 50 to 100, yes the range is 50, but 50 divided by 2 is 25. That’s not exactly the midpoint between 50 and 100. But if you do 100+50/2, you do get 75 (which is generally accepted as correct)! Well that’s pretty darn exciting.

On a side note, when I first saw this I always kept thinking, what if you get an odd number!?!? Well think about it, what does it matter if one half is unbalanced by one? The short answer is, it doesn’t! Regardless of the size, we’re still breaking each side into smaller units, and it’ll just keep right on going until it can’t be broken any more, and then it’ll start building again.

private int[] StartMergeSort(int[] intArrSource, int iL, int iR)

{

int iM;

// Set the middle
iM = iL + (iR - iL) / 2;

}

Now that we’ve got our middle, it seems like we’re all set to start breaking our array recursively into smaller parts! So let’s pass the first half, from the left to the middle, back into our function, and then we’ll pass the second half back in as well. This might seem a little redundant, but what it’s doing is the actual splitting, it’s breaking the array down into two subsets until there’s only 1 unit on the left side, and 1 unit on the right side.

private int[] StartMergeSort(int[] intArrSource, int iL, int iR)

{

int iM;

// Set the middle
 iM = (iL + iR) / 2;

// Start sorting this part of the array, looking only from the left to the middle
 intArrSource = StartMergeSort(intArrSource, iL, iM);

// Start sorting this part of the array, looking only from the middle+1 to the right
 intArrSource = StartMergeSort(intArrSource, iM, iR);

return intArrSource;

}

Now before we go any further, let’s think about some boundary cases because, well, arrays are tricky like that. Boundary cases usually occur when you iterate one to many times or when you don’t increment a variable when you should.

We’re not iterating anywhere at the moment, so do we have to increment anything? Well normally we increment when we use a variable again, and it looks like we use iM twice! So let’s increment it by one the second time we use it. This will take us from the left to the middle, and then the middle+1 to the right. Looks like we won’t have any overlaps there.

Let’s pause here for a moment, and think if this could have any unintended consequences. I like to just think through a function with some imaginary, but small, values. I prefer small values (at least for simple functions) because it’s a lot easier to think about and they inherently hit their boundary cases more quickly.

So let’s say we pass in the left boundary as 3, and the right boundary as 4. Well our middle will be (3+4)/2=4. So from left to middle it’ll sort from 4 to 4, that’ll sort one value and that’s fine. Then it’ll sort 4+1 to 4, that doesn’t seem so fine to me. How can we fix that? Well I like to start with the simplest solution first and use it until it breaks (or I need something better), so let’s just only execute our logic if the left side is less than the right side.

private int[] StartMergeSort(int[] intArrSource, int iL, int iR)

{

int iM;

// If the left index is below that of the right
 if (iL < iR)

{

// Set the middle
 iM = (iL + iR) / 2;

// Start sorting this part of the array, looking only from the left to the middle
 intArrSource = StartMergeSort(intArrSource, iL, iM);

// Start sorting this part of the array, looking only from the middle+1 to the right
 intArrSource = StartMergeSort(intArrSource, iM + 1, iR);

}

return intArrSource;

}

So far we’ve checked our boundary cases and split our units up recursively. Now we just have to do the actual sorting. We’ll do it by passing in the array, alongside it’s left, middle, and right indices.

private int[] StartMergeSort(int[] intArrSource, int iL, int iR)

{

int iM;

// If the left index is below that of the right
 if (iL < iR)

{

// Set the middle
 iM = (iL + iR) / 2;

// Start sorting this part of the array, looking only from the left to the middle
 intArrSource = StartMergeSort(intArrSource, iL, iM);

// Start sorting this part of the array, looking only from the middle+1 to the right
 intArrSource = StartMergeSort(intArrSource, iM + 1, iR);

// sort the array
 intArrSource = Sort(intArrSource, iL, iM, iR);

}

return intArrSource;

}

Now this is where things get fun, let’s dive into the Sort algorithm we just defined.

We’ll start with counters for the left, right, and merged array sets because, well, we’ve probably go to iterate when we sort.

private int[] Sort(int[] arrMerged, int iL, int iM, int iR)

{
 int iLeftCounter;
 int iRightCounter;
 int iMergedCounter;
}

Now if we’re going to be going through the left and right sides respectively, we’ll need to find out how long those sides are going to be. The left side will be the index of the middle (iM), minus the index of the left (iL), but let’s also add one because, well, array’s are zero based and we want to be inclusive.

For the right side let’s just do the right index (iR) minus the middle (iM) to get its length (basically the difference).

private int[] Sort(int[] arrMerged, int iL, int iM, int iR)

{

int iLeftCounter;
 int iRightCounter;
 int iMergedCounter;

// The left array will be from the left side, to the middle, plus 1 (so subtracting
 // the left from the middle will give us the difference between the two, and we add
 // one since arrays are zero based.
 int iLeftLength = iM - iL + 1;

// The right array will be from the middle to the right side (so substracting the
 // middle removes the entire left side
 int iRightLength = iR - iM;

}

Now that we’ve got their size, we can declare the left and right array’s, and populate them. To populate the array’s we’ll be going from their start to their end (i.e. 0 to just less than length). But what are we putting in them exactly?

Well the left array is going to hold all the values from the left index (iL) until we reach the end of the array (which remember is set to the middle-left+1).

Since the left array is going up to the middle plus one, then the right is going from the middle plus one to the end. Done and done (this part).

private int[] Sort(int[] arrMerged, int iL, int iM, int iR)

{
 int iLeftCounter;
 int iRightCounter;
 int iMergedCounter;

// The left array will be from the left side, to the middle, plus 1 (so subtracting
 // the left from the middle will give us the difference between the two, and we add
 // one since arrays are zero based.
 int iLeftLength = iM - iL + 1;

// The right array will be from the middle to the right side (so subtracting the
 // middle removes the entire left side
 int iRightLength = iR - iM;

 int[] arrLeft = new int[iLeftLength];
 int[] arrRight = new int[iRightLength];

// Copy data from the source into the Left and Right arrays
 for(iLeftCounter = 0; iLeftCounter < iLeftLength; iLeftCounter++)
{
 // Note in the merged array we're looking to go from the start of the   left
 // side up to the end of the left array (i.e. iLeftCounter < iLeftLength) 
 arrLeft[iLeftCounter] = arrMerged[iL + iLeftCounter];
 }


 for (iRightCounter = 0; iRightCounter < iRightLength; iRightCounter++)
{
 // Note we're doing the same thing here, going from the middle (+1) to
 // the end of the right array
 arrRight[iRightCounter] = arrMerged[iM + 1 + iRightCounter];
}

}

We’re re-use the counters so we’ll just set them back to zero and set the counter for the ‘merged’ array to the beginning of the area we’re sorting (i.e. the left index).

private int[] Sort(int[] arrMerged, int iL, int iM, int iR)

{

int iLeftCounter;
 int iRightCounter;
 int iMergedCounter;

// The left array will be from the left side, to the middle, plus 1 (so subtracting
 // the left from the middle will give us the difference between the two, and we add
 // one since arrays are zero based.
 int iLeftLength = iM - iL + 1;

// The right array will be from the middle to the right side (so subtracting the
 // middle removes the entire left side
 int iRightLength = iR - iM;

int[] arrLeft = new int[iLeftLength];
 int[] arrRight = new int[iRightLength];

// Copy data from the source into the Left and Right arrays
 for(iLeftCounter = 0; iLeftCounter < iLeftLength; iLeftCounter++)

{

// Note in the merged array we're looking to go from the start of the left
 // side up to the end of the left array (i.e. iLeftCounter < iLeftLength) 
 arrLeft[iLeftCounter] = arrMerged[iL + iLeftCounter];
 }


 for (iRightCounter = 0; iRightCounter < iRightLength; iRightCounter++)

{

// Note we're doing the same thing here, going from the middle (+1) to
 // the end of the right array
 arrRight[iRightCounter] = arrMerged[iM + 1 + iRightCounter];

}

// Re-initialize the counters to zero
 iLeftCounter = 0;
 iRightCounter = 0;

// Note we set the merged counter to the beginning of the left side, since that's
 // where we'll start filling in
 iMergedCounter = iL;
}

Now we’ve split up the array into left and right sections, so it’s time to put them back together. We’ll just go through them, look for the smallest values, and put them into the merged array in ascending (smallest to largest) order.

Since we’ll be going through both arrays, and we don’t know if the smallest values will be in the left or right array’s (remember, it’s still random at this point), let’s try a while loop. We’ll loop until one of the array’s is exhausted, and then carry on from that point.

For right now we can just use a simple if/else to compare the left and right array values, if we need something more complicated we’ll add it when we need it. No sense overdoing it at this stage.

private int[] Sort(int[] arrMerged, int iL, int iM, int iR)
{

int iLeftCounter;
 int iRightCounter;
 int iMergedCounter;

// The left array will be from the left side, to the middle, plus 1 (so subtracting
 // the left from the middle will give us the difference between the two, and we add
 // one since arrays are zero based.
 int iLeftLength = iM - iL + 1;

// The right array will be from the middle to the right side (so subtracting the
 // middle removes the entire left side
 int iRightLength = iR - iM;

int[] arrLeft = new int[iLeftLength];
 int[] arrRight = new int[iRightLength];

// Copy data from the source into the Left and Right arrays
 for(iLeftCounter = 0; iLeftCounter < iLeftLength; iLeftCounter++)

{

// Note in the merged array we're looking to go from the start of the left
 // side up to the end of the left array (i.e. iLeftCounter < iLeftLength) 
 arrLeft[iLeftCounter] = arrMerged[iL + iLeftCounter];
 }


 for (iRightCounter = 0; iRightCounter < iRightLength; iRightCounter++)

{

// Note we're doing the same thing here, going from the middle (+1) to
 // the end of the right array
 arrRight[iRightCounter] = arrMerged[iM + 1 + iRightCounter];

}

// Re-initialize the counters to zero
 iLeftCounter = 0;
 iRightCounter = 0;

// Note we set the merged counter to the beginning of the left side, since that's
 // where we'll start filling in
 iMergedCounter = iL; 
 
 // While neither of the left and right array's counters have surpassed their length
 while (iLeftCounter < iLeftLength && iRightCounter < iRightLength)

{

// If the value at this location in the left array is less than that in the right array
 if (arrLeft[iLeftCounter] < arrRight[iRightCounter])

{

// Then put the item in the left array into the merged array
 arrMerged[iMergedCounter] = arrLeft[iLeftCounter];
 iLeftCounter++;

}

else

{

// Otherwise put the item in the right array into the merged array
 arrMerged[iMergedCounter] = arrRight[iRightCounter];
 iRightCounter++;

}

iMergedCounter++;

}

}

Well, we could probably do this more elegantly, but for now let’s just take the while loop we just created, and break it into two. One of the left, and one for the right array. That way regardless of which array has some leftover items, those items will get put into their proper place.

 private int[] Sort(int[] arrMerged, int iL, int iM, int iR)
{
int iLeftCounter;
 int iRightCounter;
 int iMergedCounter;

// The left array will be from the left side, to the middle, plus 1 (so subtracting
 // the left from the middle will give us the difference between the two, and we add
 // one since arrays are zero based.
 int iLeftLength = iM - iL + 1;

// The right array will be from the middle to the right side (so subtracting the
 // middle removes the entire left side
 int iRightLength = iR - iM;

int[] arrLeft = new int[iLeftLength];
 int[] arrRight = new int[iRightLength];

// Copy data from the source into the Left and Right arrays
 for(iLeftCounter = 0; iLeftCounter < iLeftLength; iLeftCounter++)

{

// Note in the merged array we're looking to go from the start of the left
 // side up to the end of the left array (i.e. iLeftCounter < iLeftLength) 
 arrLeft[iLeftCounter] = arrMerged[iL + iLeftCounter];
 }


 for (iRightCounter = 0; iRightCounter < iRightLength; iRightCounter++)

{

// Note we're doing the same thing here, going from the middle (+1) to
 // the end of the right array
 arrRight[iRightCounter] = arrMerged[iM + 1 + iRightCounter];

}

// Re-initialize the counters to zero
 iLeftCounter = 0;
 iRightCounter = 0;

// Note we set the merged counter to the beginning of the left side, since that's
 // where we'll start filling in
 iMergedCounter = iL; 
 
 // While neither of the left and right array's counters have surpassed their length
 while (iLeftCounter < iLeftLength && iRightCounter < iRightLength)

{

// If the value at this location in the left array is less than that in the right array
 if (arrLeft[iLeftCounter] < arrRight[iRightCounter])

{

// Then put the item in the left array into the merged array
 arrMerged[iMergedCounter] = arrLeft[iLeftCounter];
 iLeftCounter++;

}

else

{

// Otherwise put the item in the right array into the merged array
 arrMerged[iMergedCounter] = arrRight[iRightCounter];
 iRightCounter++;

}

iMergedCounter++;

}
 
 // Notice that due to the above while loop's condition, only one of the below while 
 // loops will execute.

// If there are any items left in the left array then merge them into the merged array
 while(iLeftCounter < iLeftLength)

{

arrMerged[iMergedCounter] = arrLeft[iLeftCounter];
 iLeftCounter++;
 iMergedCounter++;

}

// If there are any items left in the right array then merge them into the merged array
 while (iRightCounter < iRightLength)

{

arrMerged[iMergedCounter] = arrRight[iRightCounter];
 iRightCounter++;
 iMergedCounter++;

}

return arrMerged;
}

And that’ll do us!

Algorithm Category: Divide & Conquer

This category is a great candidate for parallelization, as the sub-problems can be spun off onto different threads/instances/tasks. You can also build it from the bottom-up, meaning less overhead and a more organic creation of the sorted list. Moreover, it can be split by more than just two helping you balance among devices or sources (this is called multiway mergesort).

Best Case Scenario:

In the best case scenario every time two arrays are compared one is emptied before the other has any values taken out of it. So it essentially only has to compare half the values. That means we come out on the very fast end of O(n log n).

Worst Case Scenario:

At worst, every time two arrays are compared they don’t empty out until one of them has just one element left. In other words it has to compare almost every value, minus one. This means it comes out to slightly faster than O(n) time, which, you guessed, means our worse case scenario is also O(n log n)

Think about it

How would you implement this if you needed to sort a user’s tasks and show them the highest priority ones?

Note: This example can be found on github.

Leave a Reply