what is Merge sort?

Merge sort

Merge sort is the algorithm which follows divide and conquer approach. Consider an array A of n number of elements. The algorithm processes the elements in 3 steps.

1. If A Contains 0 or 1 elements then it is already sorted, otherwise, Divide A into two sub-array of equal number of elements.
2. Conquer means sort the two sub-arrays recursively using the merge sort.
3. Combine the sub-arrays to form a single final sorted array maintaining the ordering of the array.
The main idea behind merge sort is that, the short list takes less time to be sorted.


Complexity

Complexity	Best case	Average Case	Worst Case
Time Complexity	O(n log n)	O(n log n)	O(n log n)
Space Complexity			O(n)

Example :

Consider the following array of 7 elements. Sort the array by using merge sort.

1. A = {10, 5, 2, 23, 45, 21, 7}  




Algorithm

• Step 1: [INITIALIZE] SET I = BEG, J = MID + 1, INDEX = 0
• Step 2: Repeat while (I <= MID) AND (J<=END)
  IF ARR[I] < ARR[J]
  SET TEMP[INDEX] = ARR[I]
  SET I = I + 1
  ELSE
  SET TEMP[INDEX] = ARR[J]
  SET J = J + 1
  [END OF IF]
  SET INDEX = INDEX + 1
  [END OF LOOP]
  Step 3: [Copy the remaining
  elements of right sub-array, if
  any]
  IF I > MID
  Repeat while J <= END
  SET TEMP[INDEX] = ARR[J]
  SET INDEX = INDEX + 1, SET J = J + 1
  [END OF LOOP]
  [Copy the remaining elements of
  left sub-array, if any]
  ELSE
  Repeat while I <= MID
  SET TEMP[INDEX] = ARR[I]
  SET INDEX = INDEX + 1, SET I = I + 1
  [END OF LOOP]
  [END OF IF]
• Step 4: [Copy the contents of TEMP back to ARR] SET K = 0
• Step 5: Repeat while K < INDEX
  SET ARR[K] = TEMP[K]
  SET K = K + 1
  [END OF LOOP]
• Step 6: Exit
MERGE_SORT(ARR, BEG, END)

• Step 1: IF BEG < END
  SET MID = (BEG + END)/2
  CALL MERGE_SORT (ARR, BEG, MID)
  CALL MERGE_SORT (ARR, MID + 1, END)
  MERGE (ARR, BEG, MID, END)
  [END OF IF]
• Step 2: END

C Program

1. #include<stdio.h>  
2. void mergeSort(int[],int,int);  
3. void merge(int[],int,int,int);  
4. void main ()  
5. {  
6.     int a[10]= {10, 9, 7, 101, 23, 44, 12, 78, 34, 23};  
7.     int i;  
8.     mergeSort(a,0,9);  
9.     printf("printing the sorted elements");  
10.     for(i=0;i<10;i++)  
11.     {  
12.         printf("\n%d\n",a[i]);  
13.     }  
14.       
15. }  
16. void mergeSort(int a[], int beg, int end)  
17. {  
18.     int mid;  
19.     if(beg<end)  
20.     {  
21.         mid = (beg+end)/2;  
22.         mergeSort(a,beg,mid);  
23.         mergeSort(a,mid+1,end);  
24.         merge(a,beg,mid,end);  
25.     }  
26. }  
27. void merge(int a[], int beg, int mid, int end)  
28. {  
29.     int i=beg,j=mid+1,k,index = beg;  
30.     int temp[10];  
31.     while(i<=mid && j<=end)  
32.     {  
33.         if(a[i]<a[j])  
34.         {  
35.             temp[index] = a[i];  
36.             i = i+1;  
37.         }  
38.         else   
39.         {  
40.             temp[index] = a[j];  
41.             j = j+1;   
42.         }  
43.         index++;  
44.     }  
45.     if(i>mid)  
46.     {  
47.         while(j<=end)  
48.         {  
49.             temp[index] = a[j];  
50.             index++;  
51.             j++;  
52.         }  
53.     }  
54.     else   
55.     {  
56.         while(i<=mid)  
57.         {  
58.             temp[index] = a[i];  
59.             index++;  
60.             i++;  
61.         }  
62.     }  
63.     k = beg;  
64.     while(k<index)  
65.     {  
66.         a[k]=temp[k];  
67.         k++;  
68.     }  
69. }  
Output:


printing the sorted elements 

7
9
10
12
23
23
34
44
78
101

Java Program

1. public class MyMergeSort  
2. {  
3. void merge(int arr[], int beg, int mid, int end)  
4. {  
5.   
6. int l = mid - beg + 1;  
7. int r = end - mid;  
8.   
9. intLeftArray[] = new int [l];  
10. intRightArray[] = new int [r];  
11.   
12. for (int i=0; i<l; ++i)  
13. LeftArray[i] = arr[beg + i];  
14.   
15. for (int j=0; j<r; ++j)  
16. RightArray[j] = arr[mid + 1+ j];  
17.   
18.   
19. int i = 0, j = 0;  
20. int k = beg;  
21. while (i<l&&j<r)  
22. {  
23. if (LeftArray[i] <= RightArray[j])  
24. {  
25. arr[k] = LeftArray[i];  
26. i++;  
27. }  
28. else  
29. {  
30. arr[k] = RightArray[j];  
31. j++;  
32. }  
33. k++;  
34. }  
35. while (i<l)  
36. {  
37. arr[k] = LeftArray[i];  
38. i++;  
39. k++;  
40. }  
41.   
42. while (j<r)  
43. {  
44. arr[k] = RightArray[j];  
45. j++;  
46. k++;  
47. }  
48. }  
49.   
50. void sort(int arr[], int beg, int end)  
51. {  
52. if (beg<end)  
53. {  
54. int mid = (beg+end)/2;  
55. sort(arr, beg, mid);  
56. sort(arr , mid+1, end);  
57. merge(arr, beg, mid, end);  
58. }  
59. }  
60. public static void main(String args[])  
61. {  
62. intarr[] = {90,23,101,45,65,23,67,89,34,23};  
63. MyMergeSort ob = new MyMergeSort();  
64. ob.sort(arr, 0, arr.length-1);  
65.   
66. System.out.println("\nSorted array");  
67. for(int i =0; i<arr.length;i++)  
68. {  
69.     System.out.println(arr[i]+"");  
70. }  
71. }  
72. }  
Output:


Sorted array 
23
23
23
34
45
65
67
89
90
101

C# Program

1. using System;  
2. public class MyMergeSort  
3. {  
4. void merge(int[] arr, int beg, int mid, int end)  
5. {  
6.   
7. int l = mid - beg + 1;  
8. int r = end - mid;  
9.         int i,j;  
10.   
11. int[] LeftArray = new int [l];  
12. int[] RightArray = new int [r];  
13.   
14. for (i=0; i<l; ++i)  
15. LeftArray[i] = arr[beg + i];  
16.   
17. for (j=0; j<r; ++j)  
18. RightArray[j] = arr[mid + 1+ j];  
19.   
20.   
21. i = 0; j = 0;  
22. int k = beg;  
23. while (i < l && j < r)  
24. {  
25. if (LeftArray[i] <= RightArray[j])  
26. {  
27. arr[k] = LeftArray[i];  
28. i++;  
29. }  
30. else  
31. {  
32. arr[k] = RightArray[j];  
33. j++;  
34. }  
35. k++;  
36. }  
37. while (i < l)  
38. {  
39. arr[k] = LeftArray[i];  
40. i++;  
41. k++;  
42. }  
43.   
44. while (j < r)  
45. {  
46. arr[k] = RightArray[j];  
47. j++;  
48. k++;  
49. }  
50. }  
51.   
52. void sort(int[] arr, int beg, int end)  
53. {  
54. if (beg < end)  
55. {  
56. int mid = (beg+end)/2;  
57. sort(arr, beg, mid);  
58. sort(arr , mid+1, end);  
59. merge(arr, beg, mid, end);  
60. }  
61. }  
62. public static void Main()  
63. {  
64. int[] arr = {90,23,101,45,65,23,67,89,34,23};  
65. MyMergeSort ob = new MyMergeSort();  
66. ob.sort(arr, 0, 9);  
67.   
68. Console.WriteLine("\nSorted array");  
69. for(int i =0; i<10;i++)  
70. {  
71.     Console.WriteLine(arr[i]+"");  
72. }  
73. }  
74. }  
Output:


Sorted array 
23
23
23
34
45
65
67
89
90
101