Data Structures(Merge Sort in Data Structures)

 

Merge Sort:

👉  Merge Sort is a divide and conquer-based sorting algorithm.

👉  In this sorting algorithm the unsorted array keeps on dividing into two halves until the array is either empty or contains only one element, and then the halves are combined/Merged in sorted order producing a sorted array.

👉  It is one of the most popular and efficient sorting techniques.

Working of Merge sort Algorithm:

Let the elements of array are -

According to the merge sort, first divide the given array into two equal halves. Merge sort keeps dividing the list into equal parts until it cannot be further divided.

As there are eight elements in the given array, so it is divided into two arrays of size 4.

Now, again divide these two arrays into halves. As they are of size 4, so divide them into new arrays of size 2.

Now, again divide these arrays to get the atomic value that cannot be further divided.

Now, combine them in the same manner they were broken.

In combining, first compare the element of each array and then combine them into another array in sorted order.

So, first compare 12 and 31, both are in sorted positions. Then compare 25 and 8, and in the list of two values, put 8 first followed by 25. Then compare 32 and 17, sort them and put 17 first followed by 32. After that, compare 40 and 42, and place them sequentially.

In the next iteration of combining, now compare the arrays with two data values and merge them into an array of found values in sorted order.

Now, there is a final merging of the arrays. After the final merging of above arrays, the array will look like -

Now, the array is completely sorted.

Merge sort complexity

1. Time Complexity

Case	Time Complexity
Best Case	O(n*logn)
Average Case	O(n*logn)
Worst Case	O(n*logn)

2. Space Complexity

Space Complexity	O(n)
Stable	YES

Implementation of merge sort:

1. #include <stdio.h>  
2.   
3. /* Function to merge the subarrays of a[] */  
4. void merge(int a[], int beg, int mid, int end)    
5. {    
6.     int i, j, k;  
7.     int n1 = mid - beg + 1;    
8.     int n2 = end - mid;    
9.       
10.     int LeftArray[n1], RightArray[n2]; //temporary arrays  
11.       
12.     /* copy data to temp arrays */  
13.     for (int i = 0; i < n1; i++)    
14.     LeftArray[i] = a[beg + i];    
15.     for (int j = 0; j < n2; j++)    
16.     RightArray[j] = a[mid + 1 + j];    
17.       
18.     i = 0; /* initial index of first sub-array */  
19.     j = 0; /* initial index of second sub-array */   
20.     k = beg;  /* initial index of merged sub-array */  
21.       
22.     while (i < n1 && j < n2)    
23.     {    
24.         if(LeftArray[i] <= RightArray[j])    
25.         {    
26.             a[k] = LeftArray[i];    
27.             i++;    
28.         }    
29.         else    
30.         {    
31.             a[k] = RightArray[j];    
32.             j++;    
33.         }    
34.         k++;    
35.     }    
36.     while (i<n1)    
37.     {    
38.         a[k] = LeftArray[i];    
39.         i++;    
40.         k++;    
41.     }    
42.       
43.     while (j<n2)    
44.     {    
45.         a[k] = RightArray[j];    
46.         j++;    
47.         k++;    
48.     }    
49. }    
50.   
51. void mergeSort(int a[], int beg, int end)  
52. {  
53.     if (beg < end)   
54.     {  
55.         int mid = (beg + end) / 2;  
56.         mergeSort(a, beg, mid);  
57.         mergeSort(a, mid + 1, end);  
58.         merge(a, beg, mid, end);  
59.     }  
60. }  
61.   
62. /* Function to print the array */  
63. void printArray(int a[], int n)  
64. {  
65.     int i;  
66.     for (i = 0; i < n; i++)  
67.         printf("%d ", a[i]);  
68.     printf("\n");  
69. }  
70.   
71. int main()  
72. {  
73.     int a[] = { 12, 31, 25, 8, 32, 17, 40, 42 };  
74.     int n = sizeof(a) / sizeof(a[0]);  
75.     printf("Before sorting array elements are - \n");  
76.     printArray(a, n);  
77.     mergeSort(a, 0, n - 1);  
78.     printf("After sorting array elements are - \n");  
79.     printArray(a, n);  
80.     return 0;  
81. }  

Output: