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
|
void mergeSort(int* a, int low, int high)
{
if (low < high)
{
int middle = (low + high) / 2;
mergeSort(a, low, middle);
mergeSort(a, middle + 1, high);
merge(a, low, middle, high);
}
}
void merge(int* a, int low, int middle, int high)
{
int* helper = new int[high + 1 - low];
for (int index = 0; index < high + 1 - low; index++)
{
helper[index] = a[index + low];
}
int helperLeft = 0;
int helperRight = middle + 1 - low;
int current = low;
while(helperLeft <= middle - low && helperRight <= high - low)
{
if (helper[helperLeft] <= helper[helpRight])
{
a[current] = helper[helperLeft];
helperLeft++;
}
else
{
a[current] = helper[helpRight];
helperRight++;
}
current++;
}
int remaining = middle - low - helperLeft;
for (int i = 0; i < remaining; i++)
{
a[current + i] = helper[helperLeft + i];
}
delete[] helper;
}
|