-
Notifications
You must be signed in to change notification settings - Fork 2
/
merge_sort.cpp
55 lines (51 loc) · 1.13 KB
/
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
#include <iostream>
class isLess{
public:
bool operator ()(int & a, int & b) {
return a < b;
}
};
template <typename T, typename TLess>
void merge(T *a, int l, int r, TLess& isLess) {
int mid = l + (r - l) / 2;
int i = 0;
int j = 0;
T *res = new int[r - l];
while(l + i < mid && mid + j < r) {
if (isLess( a[l+i], a[mid + j]) ) {
res[i + j] = a[l + i];
i++;
} else {
res[i + j] = a[mid + j];
j++;
}
}
while(l + i < mid) {
res[i + j] = a[l + i];
i++;
}
while(mid + j < r) {
res[i + j] = a[mid + j];
j++;
}
for (int z = 0; z < r - l; z++){
a[l + z] = res[z];
}
delete []res;
}
template <typename T, typename TLess>
void mergeSort(T *a, int l, int r, TLess& isLess) {
if (l + 1 >= r)
return;
int mid = l + (r - l) / 2;
mergeSort(a, l, mid, isLess);
mergeSort(a, mid, r, isLess);
merge(a, l, r, isLess);
}
int main() {
int *a = new int[10];
for (int i = 0; i < 10; i++)
a[i] = 0;
mergeSort(a, 0, 10, isLess());
return 0;
}