Introduction
In this blog, I will be discussing Merge sort algorithm. Merge sort is a comparison based sorting algorithm based on the divide and conquer approach.
The input array will be divided into subarrays and those subarrays will be further divided until each subarray contains a single element. Then, these subarrays will be merged together to get a single sorted array.
This algorithm is asked frequently in job interviews.So first, I am going to explain Merge sort algorithm. Then, I will be providing a C# code to execute it.
Please refer to the below links for my earlier articles on sorting algorithms in C#.
The Merge Sort Algorithm
This algorithm works as follows.
- Divide the unsorted array of size N into N subarrays having single element each.
- Take two adjacent subarrays and merge them to form a sorted subarray having 2 elements.Now we have N/2 subarrays of size 2.
- Repeat the process until a single sorted array is obtained.
Let us understand this with the help of an example.
Let us take input array as - 9 8 5 7 3 1
The sorted output for this array is - 1 3 5 7 8 9
As evident from the diagram below, at each step, the array of size N is being divided into 2 subarrays of size N/2 until no further division is possible.
Step 1
At first step, the array is divided into 2 subarrays (9 8 5) and (7 3 1) of size 3 each.The subarray (9 8 5) is further divided into subarrays(9 8) and (5).The subarray (9 8) is further divided into (9) and (8). Since no further division is possible so division process will stop.Similarly, the subarray (7 3 1) from will be divided into subarrays (7 3) and (1).The subarray (7 3) is further divided into (7) and (3) and then the division process will stop.
Step 2
Since all subarrays now contain one element each, the merge process will start.Subarrays (9) and (8) will merge in sorted order to form subarray(8 9), subarrays (7) and (3) will merge to form sorted subarray (3 7). Subarrays(8 9) and (5) will merge to form sorted array (5 8 9), subarrays (3 7) and (1) will merge to form sorted array (1 3 7).Finally, subarrays (5 8 9) and (1 3 7) will merge to produce the final sorted array (1 3 5 7 8 9).
![Merge Sort Algorithm]()
Fig :- Pictorial representation of Merge Sort algorithm
Time Complexity
Merge sort is a recursive algorithm.The array of size N is divided into the maximum of logN parts, and the merging of all subarrays into a single array takes O(N) time. Hence in all the three cases (worst, average, best), the time complexity of Merge sort is O(NLogN).
Conclusion
In this tutorial, we learned about the Merge sort algorithm and its implementation using C#. Please find the attached code for better understanding.
Given below is the output screen for this code.
![Merge Sort Algorithm]()
Fig :- Output screen after running the attached code.