Divide
Split the subarray A[low..high] into two arrays A[low..middle] and A[middle+1, high].
Conquer
Sort both the subarrays A[low..high] and A[middle+1, high]. If we haven't yet reached the base case, we again divide both these subarrays and try to sort them.
Combine
When the conquer step reaches the base step and we get two sorted subarrays A[low..middle] and A[middle+1, high] for array A[low..high], we combine the results by creating a sorted array A[low..high] from two sorted subarrays A[low..middle] and A[middle+1, high].
MergeSort
The MergeSort function repeatedly divides the array into two halves until we reach a stage where we try to perform MergeSort on a subarray of size 1 i.e. low == high.
From the driver code, low(0) and high (size -1) is passed. If an array has 4 elements, low as 0 and high as 3 will be passed. Then it will be further splitted into two halves and continues until it reaches the base condition as low == high.
void mergeSort (int arr[], int low, int high) { if (low < high) { // Base Condition int middle = (high + low - 1)/ 2; mergeSort (arr, low, middle); mergeSort (arr, middle + 1, high); merge (arr, low, middle, high); } return; }
Line no 98 in the implementation would give much idea about various scenarios when MergeSort function returns.
1) When the base condition doesn't satisfy which mean high and low both are equal. Eg: (1,1), (2,2), (3,3), (4,4), (5,5)
2) After the merge calls. Eg: (1,2), (0,2), (4,5), (3,5), (0,6)
Merge
Let's deep dive by considering the following two sorted subarrays.
1. Create duplicate copies of the sub-arrays to be sorted. (Line 12 to 20)
2. Maintain current index of sub-arrays (i, j) and main array (k).
4. When we run out of elements either in L or M, place the remaining elements in combined array.
5. The below step was needed if the size of the M was greater than L.
Now, the array elements are sorted.
Mergesort Implementation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
| #include <iostream>
using namespace std;
void
merge (int arr[], int low, int middle, int high)
{
int b1Size = middle - low + 1;
int b2Size = high - middle;
int b1[b1Size], b2[b2Size];
cout << "Initialisation of First Half of Array elements: \n";
for (int i = 0; i < b1Size; i++) {
b1[i] = arr[low + i];
cout << b1[i] << " ";
}
cout << "\n\n";
cout << "Initialisation of Second Half of Array elements: \n";;
for (int j = 0; j < b2Size; j++) {
b2[j] = arr[j + middle + 1];
cout << b2[j] << " ";
}
cout << "\n\n";
int i = 0;
int j = 0;
int k = low;
while (i < b1Size && j < b2Size) {
if (b1[i] <= b2[j]) {
arr[k] = b1[i];
i++;
} else {
arr[k] = b2[j];
j++;
}
k++;
}
while (i < b1Size) {
arr[k] = b1[i];
i++;
k++;
}
while (j < b2Size) {
arr[k] = b2[j];
j++;
k++;
}
#if 1 // Debugging
cout << "Middle " << middle << " Array[" << low << "] to Array[" << high << "]\n";
for (int i = low; i <= high; i++) {
cout << arr[i] << " ";
}
cout << "\n\n";
#endif
return;
}
void
mergeSort (int arr[], int low, int high)
{
if (low < high) { // Base Condition
int middle = (high + low - 1)/ 2;
#if 1 // Debugging
cout << "High " << high << " Array[" << low << "] to Array[" << middle << "]\n";
for (int i = low; i <= middle; i++) {
cout << arr[i] << " ";
}
cout << "\n\n";
#endif
mergeSort (arr, low, middle);
#if 1 // Debugging
cout << "Low " << low << " Array[" << middle+1 << "] to Array[" << high << "]\n";
for (int i = middle + 1; i <= high; i++) {
cout << arr[i] << " ";
}
cout << "\n\n";
#endif
mergeSort (arr, middle + 1, high);
#if 1 // Debugging
cout << "Middle " << middle << " Array[" << low << "] to Array[" << high << "]\n";
for (int i = low; i <= high; i++) {
cout << arr[i] << " ";
}
cout << "\n\n";
#endif
merge (arr, low, middle, high);
}
#if 1
cout << "Returned : low " << low << " high " << high << "\n";
cout << "\n ************************** \n";
#endif
return;
}
int main ()
{
int arr[] = { 6, 5, 12, 10, 9, 1 };
int size = sizeof (arr) / sizeof (arr[0]);
cout << "Array elements before sorting: \n";
for (int i = 0; i < size; i++) {
cout << arr[i] << " ";
}
cout << "\n ************************** \n";
mergeSort (arr, 0, size-1);
cout << "\n Array elements after sorting: \n";
for (int i = 0; i < size; i++) {
cout << arr[i] << " ";
}
cout << "\n";
return 0;
} |
Output
Array elements before sorting: 6 5 12 10 9 1 ************************** High 5 Array[0] to Array[2] 6 5 12 High 2 Array[0] to Array[0] 6 Returned : low 0 high 0 ************************** Low 0 Array[1] to Array[2] 5 12 High 2 Array[1] to Array[1] 5 Returned : low 1 high 1 ************************** Low 1 Array[2] to Array[2] 12 Returned : low 2 high 2 ************************** Middle 1 Array[1] to Array[2] 5 12 Initialisation of First Half of Array elements: 5 Initialisation of Second Half of Array elements: 12 Middle 1 Array[1] to Array[2] 5 12 Returned : low 1 high 2 ************************** Middle 0 Array[0] to Array[2] 6 5 12 Initialisation of First Half of Array elements: 6 Initialisation of Second Half of Array elements: 5 12 Middle 0 Array[0] to Array[2] 5 6 12 Returned : low 0 high 2 ************************** Low 0 Array[3] to Array[5] 10 9 1 High 5 Array[3] to Array[3] 10 Returned : low 3 high 3 ************************** Low 3 Array[4] to Array[5] 9 1 High 5 Array[4] to Array[4] 9 Returned : low 4 high 4 ************************** Low 4 Array[5] to Array[5] 1 Returned : low 5 high 5 ************************** Middle 4 Array[4] to Array[5] 9 1 Initialisation of First Half of Array elements: 9 Initialisation of Second Half of Array elements: 1 Middle 4 Array[4] to Array[5] 1 9 Returned : low 4 high 5 ************************** Middle 3 Array[3] to Array[5] 10 1 9 Initialisation of First Half of Array elements: 10 Initialisation of Second Half of Array elements: 1 9 Middle 3 Array[3] to Array[5] 1 9 10 Returned : low 3 high 5 ************************** Middle 2 Array[0] to Array[5] 5 6 12 1 9 10 Initialisation of First Half of Array elements: 5 6 12 Initialisation of Second Half of Array elements: 1 9 10 Middle 2 Array[0] to Array[5] 1 5 6 9 10 12 Returned : low 0 high 5 ************************** Array elements after sorting: 1 5 6 9 10 12
Time Complexity
Best Case Complexity: O(n*log n)Worst Case Complexity: O(n*log n)
Average Case Complexity: O(n*log n)
Space Complexity
The space complexity of merge sort is O(n).
References :
Programmiz Mergesort
Comments
Post a Comment