MERGE SORT
Learning the common sorting algorithms is a great way to boost your performance. Here, I will discuss what Merge sort is, the way in which it is based on other algorithms, explain it with the help of an example, its time complexity and applications as well as its advantages and disadvantages over other algorithms.
What is Merge sort ?
Merge sort is a very important sorting technique which is based on the divide and conquer algorithm.
In divide and conquer we divide our problem into sub problems recursively till we get a problem which can be solved directly.
Similarly, Merge sort divides the array in half, sorts each of those halves, and then merges them back together. Each of those halves has the same sorting algorithm applied to it. Eventually, you are merging just two single-element arrays. It is the “merge” part that does all the heavy lifting.
How does it work ?
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.
Pseudo Code
Example
Let us take input array as — 4 8 13 2 23 16
The sorted output for this array is — 2 4 8 13 16 23
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:
The array is divided into 2 subarrays (4 8 13) and (2 23 16) of size 3 each. The subarray(4 8 13) is further divided into subarrays(4 8) and (13).The subarray (4 8) is further divided into (4) and (8). Since no further division is possible so division process will stop. Similarly, the subarray (2 23 16) will be divided into subarrays (2 23) and (16).The subarray (2 23) is further divided into (2) and (23) and then the division process will stop.
Step 2:
Since all subarrays now contain one element each, the merge process will start. Subarrays (4) and (8) will merge to form subarray(4 8), subarrays (2) and (23) will merge to form sorted subarray (2 23). Subarrays(4 8) and (13) will merge to form sorted array (4 8 13), subarrays (2 23) and (16) will merge to form sorted array (2 16 23).Finally, subarrays (4 8 13) and (2 16 23) will merge to produce the final sorted array (2 4 8 13 16 23).
Time Complexity
Merge sort is a recursive algorithm. The following recurrence relation is used to express the time complexity of merge sort:
T(n) = 2T(n/2) + θ(n)
An array of size N is divided into the maximum of logN parts, and the merging of all the subarrays into a single array takes O(N) time. Hence, in all the three cases (best, average, worse) the time complexity is O(NLogN).
Applications of Merge Sort
- It is used for sorting linked lists in O(n Log n) time.
- It can be implemented without extra space for linked lists.
- It is used for counting inversions in a list.
- It is also used in external sorting.
Advantages :
- It is quicker for larger lists because unlike insertion and bubble sort it doesn’t go through the whole list several times.
- It has a consistent running time, carries out different bits with similar times in a stage.
Disadvantages:
- Slower comparative to the other sort algorithms for smaller tasks.
- goes through the whole process even if the list is sorted (just like insertion and bubble sort)
- uses more memory space to store the sub elements of the initial split list.
