For computer grad students, sorting is the basic and most important method, which helps them to arrange the elements of an array in ascending order. Today we are going to learn about MERGE SORT which is popular for sorting in an efficient way. It is mostly used by competitive programmers(who participate in coding competitions).

So, lets start…

What is MERGE SORT??

In computer science field, MERGE SORT is an basic-purpose, efficient and comparing-based algorithm. This sorting algorithm provides/produce a stable sorting. Here stable means equal elements order is same in the produced output and given input. This algorithm uses a basic rule, which was used by many rulers to rule over a country, known as “Divide and Conquer”. This algorithm was invented by John Von Neumann in the year 1945. This can be implemented in a very efficient time complexity and its time complexity is same in all the three case i.e.

Worst Complexity — O(n*log(n))

Best Complexity — O(n*log(n))

Average Complexity — O(n*log(n))

and space complexity as n.

Logic Explanation:

We will Divide the given array/problem into two subarray/problems in every iteration, here the efficiency will increase drastically. After the completion of dividing part, we will now use Conquer, which merges the sorted subarrays into original array.

Pseudocode of MERGE SORT:

  1. First declare two variables which indicates extreme indexes of the array. For example — left and right.
  2. Now assign the left most index as 0 and right most as n-1, here n is the last index element of the array.
  3. Find the middle of the given array which will be as (right + left)/2.
  4. Now call merge sort function for the two divided arrays. Which will be as (left, mid) and the other part (mid+1, right).
  5. All the above process will iterate till the left is less than right(left<right)
  6. Then at last we will perform/send the two subproblems/arrays in merge function, where they will get merged in an single array.

MERGE SORT algorithm:

We will send Array, left and right element in the merge sort function, we will check if left is less than right, then we will find middle value and perform merge sort on two subarrays and then merge it into a single array. Else if left is greater than right, we will simply return.

merge_sort(Array, left, right){

if(left<right){

middle = (right + left)/2;

merge_sort(Array, left, middle);//recursive function

merge_sort(Array, middle+1, right);//recursive function

merge(Array, left, middle, right);

}

else{ //left>right

return;

}

}

Dry run of MERGE SORT algorithm:

Dry run 1:

Suppose we have an array of size 5. Array = 14, 12, 08, 92, 56 whose indexes are as 0, 1, 2, 3, 4. we will find the middle index value i.e. size_of_array/2 we will get it as 2 and we divide the array left part will be 14, 12, 08 and right part will be 92, 56. We perform this until we get every element as a single element. And we perform some operations and then sort it. Finally after sorting we will merge it into original array.

Array = 14, 12, 08, 92, 56

index = 0, 1, 2, 3, 4

left = 14, 12, 08. right =92, 56.

left1 = 14, 12. right1 = 08. left2 = 92. right2 = 56.

left11 = 14, right11 =12, right1 = 08, left2 = 92, right2 = 56.

Here we got every element as a single/separate element and now we perform some comparing operations and after the operations the array will look like this Array = 08, 12, 14, 56, 92. Which is sorted in an efficient manner.

Dry run 2:

Array = 78, 45, 67, 09, 11

index = 0, 1, 2, 3, 4

left = 78, 45, 67. right =09, 11.

left1 = 78, 45. right1 = 67. left2 = 09. right2 = 11.

left11 = 78, right11 =45, right1 = 67, left2 = 09, right2 = 11.

We got every element as single/separate element and we perform the same comparison operations and after the operations the array will get sorted and will merged into original array which will be as 09, 11, 45, 67, 78.

Understanding of Time Complexity:

  1. Here in the worst case also we are dividing the given array in two halves, this will be equal to log n operations performed. And this will be done for n iterative loop which will give us the exact time complexity in worst case which is (n log n).
  2. The best case will be if the array is sorted, we will have to check this by taking flag. if flag is equal to 1, then the elements are not sorted, else if 0 sorted. So the time complexity of best case will be (n log n).
  3. Average Time Complexity = O(n log n).
  4. Best Time Complexity = O(n log n).
  5. Worst Time Complexity = O(n log n).

Understanding of Space Complexity:

For the space complexity of merge sort we need n auxiliary space because the size of the array will be n and all these elements are copied to that auxiliary space, hence the space complexity is O(n).

Code of MERGE and MERGE SORT:

#include<stdio++.h>

void merge(Array, start, middle, last){

long long int length_of_first_half = (middle - start)+1;

long long int length_of_secong_half = (last - middle);

long long int left_array[length_of_first_half];

long long int right_array[length_of_secong_half];

long long int i = 0;

while(i<length_of_first_half){

left_array[i] = Array[start + i];

}

for(long long int j = 0; j<length_of_secong_half; j++){

right_array = Array[middle + 1 + j];

}

long long int x, y, z;

while(x<length_of_first_half && y<length_of_secong_half){

if(left_array[x] >right_array[y]){

Array[z] = right_array[y];

y++;

}

else{

Array[z] = left_array[x];

x++;

}

z++;

}

while(x<length_of_first_half){

Array[z] = left_array[x];

x++;

z++;

}

while(y<length_of_secong_half){

Array[z] = right_array[y];

y++;

z++;

}

}

void merge_sort(Array, left, right){

if(left<right){

middle = (right + left)/2;

merge_sort(Array, left, middle);//recursive function

merge_sort(Array, middle+1, right);//recursive function

merge(Array, left, middle, right);

}

else{ //left>right

return;

}

}

void printing(Array, s);

int main(){

long long int Array[] = {8, 9, 5, 12, 2};

long long int s = sizeof(Array)/sizeof(Array[0]);

long long int l = 0;

merge_sort(Array, l, s-1);

printing(Array, s);

}

void printing(Array, s){

long long int i = 0;

while(i<s){

cout<<Array[i]<<endl;

}