/
4. Merge Sort.cpp
74 lines (60 loc) · 1.36 KB
/
4. Merge Sort.cpp
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
#include <iostream>
using namespace std;
// Function for merging two sorted arrays.
void merge(int *arr, int start, int mid, int end) {
int n1 = mid - start + 1;
int n2 = end - mid;
int lArr[n1];
int rArr[n2];
for(int i = 0; i < n1; i++) {
lArr[i] = arr[start + i];
}
for(int i = 0; i < n2; i++) {
rArr[i] = arr[mid + i + 1];
}
int i = 0;
int j = 0;
int k = start;
while(i < n1 && j < n2) {
if(lArr[i] <= rArr[j]) {
arr[k] = lArr[i];
i++;
} else {
arr[k] = rArr[j];
j++;
}
k++;
}
while(i < n1) {
arr[k] = lArr[i];
k++;
i++;
}
while(j < n2) {
arr[k] = rArr[j];
k++;
j++;
}
}
// Function for merge Sort.
void mergeSort(int *arr, int start, int end) {
if(end > start) {
int mid = start + (end - start)/2;
mergeSort(arr, start, mid);
mergeSort(arr, mid + 1, end);
merge(arr, start, mid, end);
}
}
// Main Function
int main() {
int arr[] = {4,2,5,7,3,1,0,6,-1};
cout << "Array Before Sorting : " << endl;
for(auto num : arr) {
cout << num << "\t";
}
mergeSort(arr, 0, 8);
cout << endl << "Array After Sorting (Merge Sort) : " << endl;
for(auto num : arr) {
cout << num << "\t";
}
}