Merge Sort Algorithm

Merge Sort is considered to be one of the most respected, popular, as well as an efficient algorithm that is used by programmers all around the globe for sorting purposes. The merge sort algorithm was invented by John von Neumann in 1945.

Merge sort is based on the principle of Divide and Conquer Algorithm. Talking about the algorithm, in merge sort, we repeatedly breakdown the given array into subarrays. We keep on dividing until we reach the condition where the size of each subarray is equal to one or, each subarray contains a single element. After that, we start merging the subarrays in a manner such that we get the sorted array as our final result. Now, first of all, let us get a brief idea about the Divide and Conquer Algorithm.

Merge Sort is also a Stable Algorithm i.e. it produces a stable sort. It means that if two elements are equal then their order remains same in the input as well as output.

Divide and Conquer Algorithm

In the divide and conquer algorithm, first, we break the original problem into multiple subproblems. After this, we use recursion to solve the subproblems one by one. And then finally, we combine the solutions of the subproblems to get the result of the original problem. Now technically if we analyze, we can break the divide and conquer algorithm into three parts: divide, conquer and combine.

Divide: Int this we divide the problem into sub-problems, which are the smaller instances of the original problem.

Conquer: In this step, we solve each subproblems using recursion. When small enough, then subproblems are solved as base cases.

Combine: In this final step, the solutions of each subproblem are combined to get a single solution as the final result of the original problem.

Now, some important points to be remembered is that each subproblem must be less than the original problem since we are dividing the original problem into smaller instances. And also, since we are using recursion to solve the subproblems, each subproblem must have a base case.

How Merge Sort Works?

Since merge sort works with the divide and conquer paradigm, we follow the basic rules of divide and conquer algorithm in merge sorting that is, 1) Divide 2) Conquer, and 3) Combine.

At first, we divide the given array midway into 2 equal subarrays. We continue this process of dividing the subarrays into two halves until the size of each subarray becomes one or each subarray consist of a single element. The idea behind this is that an array with a single element is always sorted, so once we have divided the array into multiple subarrays with a single element, we have reached our base subproblem.

After dividing the array into multiple subarrays of size one and reaching the base condition, we start merging the sorted subarray one by one to form a single array and hence getting the final result in the form a single sorted array.

The following steps are followed:-

1. we take two variables s and e. we store the starting index in variable s and the last index of the given array in the variable e.
2. Then we find the middle index by the formula (s + e)/2 and store the index in the variable m.
3. Then we break the array into two subarrays, whose starting and ending index are from s to m and from m+1 to e.
4. Now we similarly continue to divide each subarray into two further smaller instances by finding the starting, ending, and middle index. We recursively keep on breaking down until the size of each subarray is one.
5. In the final step, we start merging the two sublists at a time, while comparing each element of the sublist and storing them in a sorted manner.

Understanding Merge Sort By an Example

Lets’ consider the array with elements [14,7,3,12,9,11,6,12]. The size of the array is 8. In the first step, we are storing the first index 0 and the last index i.e. 7 in the variables p and r respectively. After this, we are finding the middle index by the formula (p + r)/2 and storing the result in variable q.

After getting the value for p, q and r we finally divide the array into two subarrays i.e. from index p to q and from q+1 to r respectively. Subarray 1 with elements from 14 to 12 and subarray 2 with elements from 9 to 2. Now we continue to repeat the above steps i.e. dividing each of the subarrays into 2 halves recursively until we reach the base case where the size of each subarray is one.

After we reach the base condition, we begin with merging the subarrays two at a time, while comparing each element of the subarray and arranging them sorted manner. 2 of the sublists formed at the last dividing step are [14] and [7]. We merge the two sublists after comparing them and get [7,14] as sorted array. We apply this logic to every other subarray and finally get the single sorted array as a result i.e. [2,3,6,7,9,11,9,11,12,14].

Implementation

We use mainly two functions for the implementation of the merge sort algorithm.

1. mergeSort()
2. merge()

mergeSort()

In this function, we divide the arrays and subarrays into two parts recursively until the size of each subarray is one.

Implementation is shown below in CPP.

void mergeSort(int a[],int s, int e){

if(s>=e){

return;

}

int mid = (s+e)/2; //find the middle position

mergeSort(a,s,mid); //sort first and second halves

mergeSort(a,mid+1,e);

merge(a,s,mid,e);

}

merge()

In this function, we will merge subarrays together by taking two at a time while comparing each of the elements of both the arrays and storing them in a sorted manner.

Implementation is shown below in CPP.

void merge(int a[],int s,int mid,int e){

int n1 = mid — s + 1;

int n2 = e — mid;

int sub1[n1],sub2[n2]; //Create temp arrays

for(int i=0;i<n1;i++){ // copy the elements to temp arrays sub1[] sub2[]

sub1[i] = a[s+i];

}

for(int i=0;i<n2;i++){

sub2[i] = a[mid+1+i];

}

int i=0,j=0,k=s;

// merge the temp arrays back into original array a[]

while(i<n1 && j<n2){

if(sub1[i]<=sub2[j]){ // finding the smaller element

a[k]=sub1[i];

i++;

}

else if(sub1[i] > sub2[j]){ // finding the smaller element

a[k] = sub2[j];

j++;

}

k++;

}

while(i<n1){ // copy the remaining elements of sub1[] if any

a[k] = sub1[i];

i++;

k++;

}

while(j<n2){ // copy the remaining elements of sub2[] if any

a[k] = sub2[j];

j++;

k++;

}

}

Time Complexity

Merge sort is a Recursive Algorithm. Therefore, the time complexity of Merge Sort can be expressed using recurrence relation i.e. T(n) = 2T(n/2) + θ(n).

We can solve this recurrence relation using the Recurrence Tree method or the Master method. And the solution after solving we get is θ(nLogn). The time complexity of merge sort is θ(nLogn) in all three cases i.e. worst, average, and best.

Auxiliary Space

The Auxiliary Space for Merge Sort Algorithm is O(n).

Applications

1. Linked list can be sorted in O(nLogn) time by using Merge Sort.
2. We can solve Inversion Count Problem using Merge Sort.
3. Merge Sort is used in External Sorting.

Drawbacks of Merge Sort Algorithm

1. As compared to other algorithms merge sort is a bit slower.
2. Additional memory space of 0(n) is required for the temporary array.
3. Not suitable when the array is already sorted.