-
Notifications
You must be signed in to change notification settings - Fork 0
/
Merge Sort
91 lines (78 loc) · 2.16 KB
/
Merge Sort
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
#include <iostream>
using namespace std;
void merge(int arr[], int s, int e) {
int mid = s + (e-s)/2;
int leftLength = mid - s + 1;
int rightLength = e - mid;
int *leftArr = new int[leftLength];
int *rightArr = new int[rightLength];
// Copy data to temp arrays
for(int i = 0 ; i < leftLength ;i++) {
leftArr[i] = arr[s + i];
}
for(int i = 0 ; i < rightLength ; i++) {
rightArr[i] = arr[mid + 1 + i];
}
// sorting and updation of main array
int leftArrIndex = 0;
int rightArrIndex = 0;
//yahi pr galti hoti hai ---> be careful
int mainArrIndex = s;
while(leftArrIndex <leftLength && rightArrIndex <rightLength){
if(leftArr[leftArrIndex] < rightArr[rightArrIndex]){
arr[mainArrIndex] = leftArr[leftArrIndex];
leftArrIndex++;
mainArrIndex++;
}
else{
arr[mainArrIndex] = rightArr[rightArrIndex];
rightArrIndex++;
mainArrIndex++;
}
}
// Copy remaining elements of left array if any
while(leftArrIndex<leftLength){
arr[mainArrIndex] = leftArr[leftArrIndex];
leftArrIndex++;
mainArrIndex++;
}
// Copy remaining elements of right array if any
while(rightArrIndex<rightLength){
arr[mainArrIndex] = rightArr[rightArrIndex];
rightArrIndex++;
mainArrIndex++;
}
delete [] leftArr;
delete [] rightArr;
}
void mergeSort(int arr[], int s, int e) {
int mid = s + (e - s) / 2;
if (s >= e) {
return;
}
// Recusrsive call for left array
mergeSort(arr, s, mid);
// Recusrsive call for right array
mergeSort(arr, mid + 1, e);
// merge two sorted arrays
merge(arr, s, e);
}
int main() {
//int arr[] = {2, 1, 9, 7, 4, 6};
int arr[] = {1,1,1,1,12,1,0};
int size = sizeof(arr) / sizeof(arr[0]);
int start = 0;
int end = size - 1;
//arr before merge sort
cout << "Array before merge sort: ";
for(auto it: arr){
cout<<it << " ";
}
cout<<endl;
mergeSort(arr, start, end);
//arr after merge sort
cout<<"Array after merge sort: ";
for(auto it: arr){
cout<<it << " ";
}
}