INTRODUCTION

EXPLANATION

Suppose we have an of length n. Now we have to follow the below mention step to sort an array.
Divide the array of length n into the two-part first one of the size of n/2 and the second one of the n-n/2 length. we can call the first part a left half part and the second part a right half part respectively.
Then we can call the recursive sort function to sort the left half part and right half part.
Then we have to call the merge function to merge both half arrays after that we got a fully sorted array.

Now I will explain to you the merge sort with the help of an example.
suppose we have an array : [7,5,6,2,3,8,4]
firstly, as mention in the above step one we have to divide the array into two parts so the following arrays will be manufactured as a right half and a left half respectively:
right half: [7,5,6,2]
left half:[3,8,4]
Then as mention in step two, we have to call a recursive function to sort the right half and the left half arrays. then we will get the following sub-arrays:
Recursively sorted left half: [2,5,6,7]
Recursively sorted right half: [3,4,8]

At last as mention in step three, we have to combine these two subarrays to create the final sorted array.
final sorted array:[2,3,4,5,6,7,8]
As we know the left half and right half sub-array can be sorted using recursion with the help of below mention algorithm. The fantastic thing occurs when we get the final sorted and merged array. We can grasp a good hold on this topic with the help of examples.
In the above mention example, we have two arrays [2,5,6,7] and [3,4,8]. Actually, we have to merge these two sorted arrays. let put pointer on the 0 th index in both the arrays.
Final merged array = []
Left array: [2, 5, 6, 7]
Right array: [3, 4, 8]
As we can see in the above example the point of the left array is at 2 and the pointer on the right array is at 3. we have to grasp the smaller element and put it into the final merged array and then we have to increment the pointer of that array from which we have chosen the smaller element. After performing this operation we have below mention condition:
Final merged array = [2]
Left array: [5, 6, 7]
Right array: [3, 4, 8]
By following above mention step i.e pointer is pointing in the left array at 5 and the pointer is pointing in the right array at 3 now we have again compared and found out the smallest element and put it into a final merged array and then we have to increment the pointer of that array from which we have to choose the smaller element. After performing this operation we have below mention condition:
Final merged array = [2, 3]
Left array: [5, 6, 7]
Right array: [4, 8]
We repeat the above mention step again to get:
Final merged array = [2, 3, 4]
Left array: [5, 6, 7]
Right array: [8]
ongoing with this exercise, we can see that we are fortunately able to get the final merged array in the sorted form:
Final merged array = [2, 3, 4, 5, 6, 7,8]
Left array: []
Right array: []

From the beginning to the end we can see that we have conveniently converted unsorted array to sorted array. But some of you thinking that how the left array and right arrays have been sorted? the answer is we used recursion using the same technique as above mentioned. to make it more clear consider an example of the right array: [3, 8, 4]. To sort it, we will divide it again into two sub-arrays: [3, 8] and [4]. Both these sub-arrays are already sorted so we can simply merge them by using the merging technique explained above mention example to get the sorted array [3, 4, 8].

Now consider the following image to get better clarity on this topic:

from the above image, we can see that the actual array is breaking down into sub-arrays. when we have divided the whole array into a single-element array after that we got merged and sorted the array. Let us understand the detailed steps involved in merge sort.

  • [38, 27, 43, 3, 9, 82, 10] is divided into [38, 27, 43, 3] and [9, 82, 10]
  • [38, 27, 43, 3] is divided into [38, 27] and [43, 3]
  • [38, 27] is divided into [38] and [27]
  • [38] is a single element array and so, is sorted.
  • [27] is a single element array and so, is sorted.
  • [38] and [27] are merged into [27, 38]
  • [43, 3] is divided into [43] and [3]
  • [48] is a single element array and so, is sorted.
  • [3] is a single element array and so, is sorted.
  • [3] and [48] are merged into [3, 48]
  • [27, 38] and [3, 48] are merged into [3, 27, 38, 48]
  • [9, 82, 10] is divided into [9, 82] and [10]
  • [9,82] is divided into [9] and [82]
  • [9] is a single element array and so, is sorted.
  • [82] is a single element array and so, is sorted.
  • [9] and [82] are merged into [9, 82]
  • [10] is a single element array and so, is sorted.
  • [9, 82] and [10] are merged into [9, 10, 82]
  • [3, 27, 38, 48] and [9, 10, 82] are merged into [3,9,10,27,38,43,82].

So in this way merge sort work. for your more understanding i am attaching here one animation also:

Merge Sort Pseudo Code

function merge_sort(i, j, a, aux) {
mid = (i + j) / 2
merge_sort(i, mid, a, aux)
merge_sort(mid + 1, j, a, aux)
pointer_left = i, pointer_right = mid + 1
for k in [i ... j] {
if pointer_left points to smaller element, aux[k] = a[pointer_left] and increment pointer_left by 1
if pointer_right points to smaller element, aux[k] = a[pointer_right] and increment pointer_right by 1
}
copy the contents of aux[i .. j] to a[i .. j]
}

Merge Sort Program in C++

#include<iostream>
using namespace std;
void swapping(int &a, int &b) { //swap the content of a and b
int temp;
temp = a;
a = b;
b = temp;
}
void display(int *array, int size) {
for(int i = 0; i<size; i++)
cout << array[i] << " ";
cout << endl;
}
void merge(int *array, int l, int m, int r) {
int i, j, k, nl, nr;
//size of left and right sub-arrays
nl = m-l+1; nr = r-m;
int larr[nl], rarr[nr];
//fill left and right sub-arrays
for(i = 0; i<nl; i++)
larr[i] = array[l+i];
for(j = 0; j<nr; j++)
rarr[j] = array[m+1+j];
i = 0; j = 0; k = l;
//marge temp arrays to real array
while(i < nl && j<nr) {
if(larr[i] <= rarr[j]) {
array[k] = larr[i];
i++;
}else{
array[k] = rarr[j];
j++;
}
k++;
}
while(i<nl) { //extra element in left array
array[k] = larr[i];
i++; k++;
}
while(j<nr) { //extra element in right array
array[k] = rarr[j];
j++; k++;
}
}
void mergeSort(int *array, int l, int r) {
int m;
if(l < r) {
int m = l+(r-l)/2;
// Sort first and second arrays
mergeSort(array, l, m);
mergeSort(array, m+1, r);
merge(array, l, m, r);
}
}
int main() {
int n;
cout << "Enter the number of elements: ";
cin >> n;
int arr[n]; //create an array with given number of elements
cout << "Enter elements:" << endl;
for(int i = 0; i<n; i++) {
cin >> arr[i];
}
cout << "Array before Sorting: ";
display(arr, n);
mergeSort(arr, 0, n-1); //(n-1) for last index
cout << "Array after Sorting: ";
display(arr, n);
}

OUTPUT

Enter the number of elements: 6
Enter elements:
14 20 78 98 20 45
Array before Sorting: 14 20 78 98 20 45
Array after Sorting: 14 20 20 45 78 98

Merge Sort Complexity

Complexity gives the idea of the time taken to execute the algorithm as a function of the size of the input. For example, suppose T(n) be the time taken to perform merge sort on an array of size n.

So we can see, that T(n) comprises 3:

  1. Time spent in performing merge sort on the left half. The left half is of size n/2 and so, the time spent would be T(n/2).
  2. Time spent in performing merge sort on the right half. The right half is of size n/2 and so, the time spent here would also be T(n/2).
  3. Time spent in merging the left and the right halves. Basically, to merge the 2 halves, we place pick each element one-by-one from the 2 subarrays and fill in the original array. Since there are n elements, the time taken in merging would be proportional to n. So, let us call this time as cn where c is some constant.

Total time, T(n) = T(n/2) + T(n/2) + cn

So, we have the equation as: T(n) = 2T(n/2) + cn. With some maths, this equation can be solved as

T(n) = 2T(n/2) + cn

By solving above equation we will get

T(n)=O(nlogn)

Conclusion

Merge sort is a very engrossing algorithm and forms a great case-study to understand data structures and algorithms. Also, it has the lowest complexity as compared to other comparison-based sorting algorithms like the bubble sort, insert sort and selection sort they all have O(n²) complexity while it has only O(N log N) time complexity.

REFRENCES

  1. https://www.geeksforgeeks.org/merge-sort/
  2. https://www.tutorialspoint.com/data_structures_algorithms/merge_sort_algorithm.htm
  3. https://www.youtube.com/watch?v=XaqR3G_NVoo&list=RDQMmHirsc-1Mg8&start_radio=1