Hell Friends, In the series to complete all the sorting algorithm, this is my new article to explain merge sort algorithm in C# with step by step easy explanation. First I will help you to analyze the merge sort algorithm with the help of flow char in figure. And then I will give you C# code.
Below are the links to know about other sorting algorithms
- Selection sort Algorithm in C#
- Insertion sort algorithm in C#
- Quick sort algorithm in C#
- Bubble sort algorithm in C#
Merge Sort Algorithm in C#
Merge sort is a very good example of divide and conquer strategy of algorithm. And the implementation is also based on the recursive programming principle.
As always I will start with an example and try to explain the Merge sort algorithm with the help of that example.
Let’s take an array as example as shown in the step1 in below figure. The array is {6,4,3,7,5,1,2}.
Now the first step in this algorithm is to divide the array in half and keep dividing the subsequent resulting arrays till we get individual. I am doing the same from step1 to step4.
Now once we are done with dividing the array till individual element, we will start creating the arrays out of these elements by comparing and combining them.
For example, in step4, elements 6 and 4 are compared and added in ascending order resulting an array {4.6}. Similarly 3 and 7 are compared and added to create an array {3,7}. Similarly for the rest of the elements.
Once we have small arrays at step5 we will combine the sub array to get a sorted array.
And this combination is done by comparing the first element off the sub array. After step5, element 4 and 3 are compared out of which 3 is sent to the bigger array. Now 4 and 7 are compared sending 4 to bigger array. Finally 6 and 7 are compared and added to bigger array as in step6.
Similarly another array is created with elements {1,2,5}.
And finally in step 7 both of these arrays are combined to create the final array.
Code for Merge Sort Algorithm in C#
private static void MergeSort()
{
int[] arr = { 6, 4, 3, 7, 5, 1, 2 };
Array.ForEach(DivideTheArrayInTwo(arr), i => Console.WriteLine(i));
}
private static int[] DivideTheArrayInTwo(int[] arr)
{
int centre = 0;
bool isOdd = false;
if (arr.Length == 1)
return arr;
if(arr.Length % 2 == 0)
{
centre = arr.Length / 2;
}
else
{
centre = (arr.Length - 1) / 2;
isOdd = true;
}
int[] firstHalf = new int[centre];
int[] secondHalf;
if (isOdd)
secondHalf = new int[centre + 1];
else
secondHalf = new int[centre];
Array.Copy(arr, firstHalf, centre);
if(!isOdd)
Array.Copy(arr, centre, secondHalf, 0, arr.Length - centre);
else
Array.Copy(arr, centre, secondHalf, 0, arr.Length - centre);
firstHalf = DivideTheArrayInTwo(firstHalf);
secondHalf = DivideTheArrayInTwo(secondHalf);
int[] sortedArray = new int[firstHalf.Length + secondHalf.Length];
int i = 0;
int j = 0;
int pos = 0;
while (pos < sortedArray.Length)
{
if (i < firstHalf.Length && j < secondHalf.Length)
{
if (firstHalf[i] > secondHalf[j])
{
sortedArray[pos++] = secondHalf[j++];
}
else
{
sortedArray[pos++] = firstHalf[i++];
}
}
else
{
if (i == firstHalf.Length && j < secondHalf.Length)
{
sortedArray[pos++] = secondHalf[j++];
}
else if (j == secondHalf.Length && i < firstHalf.Length)
{
sortedArray[pos++] = firstHalf[i++];
}
}
}
return sortedArray;
}Run Time Analysis of Merge Sort
At the top level, we have 1 list with n elements. For simplicity, let’s assume n is a power of 2. At the next level there are 2 lists with n/2 elements. Then 4 lists with n/4 elements, and so on until we get to n lists with 1 element.
On every level we have a total of n elements. On the way down, we have to split the arrays in half, which takes time proportional to n on every level. On the way back up, we have to merge a total of n elements, which is also linear.
If the number of levels is h, the total amount of work for the algorithm is O(nh). So how many levels are there? There are two ways to think about that:
- How many times do we have to cut n in half to get to 1?
- Or, how many times do we have to double 1 before we get to n?
Another way to ask the second question is, “What power of 2 is n?”
Taking the log(base2) of both sides yields
So the total time is O(n log n).