Merge Sort and it's time complexity
Data Structure Notes

Merge Sort Algorithm

Merge Sort and It’s Time Complexity

Merge sort and it’s time complexity make it more useable sorting algorithm in Data structure. In this article we will discuss about Merge Sort algorithm and it”s time complexity.

Questions based on merge sort are generally asked in GATE(CS) and UGC NET exam.

In this tutorial we will discuss merge sort algorithm, merge sort times complexity and we will also learn about working of merge sort algorithm along with merge sort program in C Programming Language

So let’s start with introduction of merge sort algorithm.

What is Merge Sort Algorithm ?

  • Merge sort is a Sorting Techniques that follow Recursive and Divide and Conquer Approach.
  • The divide and conquer strategy says that if a list is large then divide the complete list into sub-lists.
  • We’ll keep dividing the list into sub-lists until each sub-list is having one element. Then we’ll merge the sub-lists into one list until we have a sorted list.

Pseudo Code for Merge Sort Algorithm is given below

In the following algorithm, ar is the given array, begin is the starting element, and ends is the last element of the array.

MERGE_SORT(ar, begin, ends)

if begin < ends

set mid = (begin + ends)/2

MERGE_SORT(ar, begin, mid)

MERGE_SORT(ar, mid + 1, ends)

MERGE (arr, begin, mid, ends)

end of if

END MERGE_SORT

MERGE function written in above pseudo code is an important part of merge  sort algorithm.

This MERGE unction performs the merging of two sorted sub-arrays that are Ar[begin…mid] and Ar[mid+1…ends] and build  one sorted array A[begin…ends]s.  A[], begin, mid, and ends are the input of merge function,

The implementation of the MERGE function in c programming is given as follows –

void mergesort(int ar[], int begin, int mid, int ends)

{

int a,b, c;

int n1 = mid – begin + 1;

int n2 = ends – mid;

int LeftArray[n1], RightArray[n2]; // these are temporary arrays

/* now copy data item to these temp arrays */

for (int  a= 0; a < n1; a++)

LeftArray[i] = ar[begin + i];

for (int b = 0; b < n2; b++)

RightArray[j] = ar[mid + 1 + j];

a= 0, /*this is initial index of first sub-array */

b= 0; /*this is  initial index of second sub-array */

c = begin;  /*this is  initial index of merged sub-array */

while ( a< n1 && b< n2)

{

if(LeftArray[a] <= RightArray[b])

{

ar[c] = LeftArray[a];

a++;

}

else

{

ar[c] = RightArray[b];

b++;

}

c++;

}

while (a<n1)

{

ar[c] = LeftArray[a];

a++;

c++;

}

while (b<n2)

{

ar[c] = RightArray[b];

a++;

c++;

}

}

Working of Merge Sort Algorithm Example

Let us try to understand the working of merge sort algorithm with a simple example-

Consider an Array Data Structure A  given below . Array consist 8 elements which are in unsorted order. Now we have to sort this array in increasing order using merge sort algorithm.

Merge Sort and it's time complexity

Step 1 – First we’ll divide this array into two equal sub arrays.

Step 2- First we need to find out the mid position of the array and we’ll divide the array from the mid position. Here mid position would be

Merge Sort and it's time complexity

Hence from position 0 to 4, we have one sub list and from 5 to 7another sub list.

Merge Sort and it's time complexity

Step 3 – Again we’ll divide both the left and the right sub list into two sub lists again.

Step 4 – We’ll keep dividing until we find a sub list with only one element.  In the left sub list the mid element is 0+4/2=2nd position.

In the right sub list the mid element is 5+7/2=12/2=6th position.

We can’t further divide the sub lists when each sub list will have only one element.

Then we are going to merge these sorted sub lists which will again produce a complete sorted list.

Point To Remember – If there is ‘m’ no. of elements in the left sub list and ‘n’ elements in the right sub list, time complexity of merging these sub lists is Θ(m+n).

  • If we denote left sub list as ‘L’ and the right sub list as ‘R’, then while merging these two sub list we need to compare 1st element of L with 1st element of R; i.e. we need to compare Li with Rj.
  • The element which is the smallest will come first and we’ll keep comparing elements till we get a sorted list.
  • Whole process of merge sort algorithm discuss in above steps is as shown in Figure.

Merge Sort and it's time complexity

Merge Sort’s Time complexity

For  n no. of elements in an array time taken by a merge sort algorithm is Θ(n Log(n)).

 Merge Sort Program in C

Some time in Technical Interview , along with Merge Sort and it’s time complexity interviewer  also ask to write a prom in c for merge sort. So in this section we are going to tell you how to write a merge sort  program in c to implement the merge sort algorithm.

Students are requested to run this c program and perform the merge sort.

#include <stdio.h>

#include<conio.h>

/* first we implement Function to merge the subarrays of a[] */

void merge(int a[], int begin, int mid, int ends)

{

int i, j, k;

int m1 = mid – begin + 1;

int m2 = ends – mid;

int LFA[m1], RA[m2]; //LFA is Left Array and RA is RightArray , these are temporary arrays

/* copy data to temp arrays */

for (int i = 0; i < m1; i++)

LFA[i] = a[begin + i];

for (int j = 0; j < m2; j++)

RA[j] = a[mid + 1 + j];

i = 0; /* initial index of first sub-array */

j = 0; /* initial index of second sub-array */

k = begin;  /* initial index of merged sub-array */

while (i < m1 && j < m2)

{

if(LFA[i] <= RA[j])

{

a[k] = LFA[i];

i++;

}

else

{

a[k] = RA[j];

j++;

}

k++;

}

while (i<m1)

{

a[k] = LFA[i];

i++;

k++;

}

while (j<m2)

{

a[k] = RA[j];

j++;

k++;

}

}

void mergeSort(int a[], int begin, int ends)

{

if (begin < ends)

{

int mid = (begin + ends) / 2;

mergeSort(a, begin, mid);

mergeSort(a, mid + 1, ends);

merge(a, begin, mid, ends);

}

}

/* Function to print the array */

void printArray(int a[], int n)

{

int i;

for (i = 0; i < n; i++)

printf(“%d “, a[i]);

printf(“\n”);

}

int main()

{

int a[] = { 12, 31, 25, 8, 32, 17, 40, 42 };

int n = sizeof(a) / sizeof(a[0]);

printf(“Enter the array elements – \n”);

printArray(a, n);

mergeSort(a, 0, n – 1);

printf(“Array elements after sorting  are – \n”);

printArray(a, n);

return 0;

}

Output

When we will run the above program then we will get the following output.

Enter the array elements

15 16 2 19 35 26 21  4

After Sorting Array element s are

2 4 15 16 19 21 26 35

Conclusion and Summary

  • I hope after reading this merge sort and it’s time complexity tutorial students will be able to do the problem based on merge sort.
  • Students can apply the merge sort concepts in sorting the data.
  • We have also discussed the merge sort program in c

If you have any query regarding the merge sort and it’s time complexity related this article then you may ask in comment section.

Leave a Reply

Your email address will not be published. Required fields are marked *