What is Merge Sort Algorithm in Data Structures? | Data Structures Tutorial

In this article, you will understand the merge sort algorithm in the data structures in brief. 

It is a very popular sorting algorithm that is based on the principle of Divide and conquers. In divide and conquer, a problem is divided into smaller sub-problems. Each sub-problem is solved independently. Then they are combined to form the final solution. 

Divide and Conquer Strategy

In the divide and conquer strategy, we divide a big problem into smaller subproblems. When we solve each sub-problem individually, then we combine the output of each subproblem into one. It divides the array into two halves until we reach a stage where we try to perform on a subarray of size 1. After this, the merge functions come into play and start combining the sorted arrays into larger arrays until the entire array is merged. 

Merge Sort Algorithm

The difference between the merging step and merge sort is that we only perform the merge function on consecutive subproblems. Because of this, we only need the array, the first position and last position of the first subarray, and the last element index of the second subarray. 

The task is to merge the subarrays X[p…q] and X[q+1…s] to sort the array X[p….s]. The inputs of the merge function are X, p, q, and s. 

Working on merge function

1. From the copies of the subarrays A <- X[p…q] and B<- X[p+1…s].
2. Make three-pointers i, j, and k.
1. i is the current index of A, starting with 1. 
2. j is the current index of B, starting with 1.
3. k is the current index of A[p..r], starting with p.
3. Till we point to the end of either A or B, pick the largest among the elements from A and B and put them in the particular position at X[p…q].
4. When we run out of the elements in either L or M, pick up the remaining elements and place them in X[p…q].

How is the merge function executed?

1. Create the replica of the sub-arrays to be sorted.
2. Maintain a current index of sub-arrays and main arrays.
3. Unless we approached the end of either A or B, choose larger among elements A and B and put them in the correct position at X[p…s].
4. When we run out of elements in either A or B, choose the leftover elements and put in X[p…s]

Complexity

Time complexity

The best case complexity is O(n*log n), the average case complexity is O(n*log n), and the worst case complexity is O(n*log n). 

Space complexity is O(n).

Applications of Merge Sort

• It is used in solving the inversion count problem
• It is used in external sorting.
• It is used in e-commerce applications