PrometheusAlgorithms/MergeSort.h at master · vyefremov/PrometheusAlgorithms · GitHub

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 <limits>

void Merge(int * A, unsigned int p, unsigned int q, unsigned int r){
	unsigned int s1 = q - p + 1;
	unsigned int s2 = r - q;

	int * L = new int[s1];
	int * R = new int[s2];

	for (unsigned int i = 0; i < s1; i++) {
		L[i] = A[p + i];
	}

	for (unsigned int i = 0; i < s2; i++) {
		R[i] = A[q + i + 1];
	}

	L[s1] = std::numeric_limits<int>::max();
	R[s2] = std::numeric_limits<int>::max();

	unsigned int i = 0;
	unsigned int j = 0;

	for (unsigned int k = p; k < r + 1; k++) {
		if (L[i] <= R[j]){
			A[k] = L[i];
			i++;
		}
		else{
			A[k] = R[j];
			j++;
		}
	}

	delete[] L;
	delete[] R;
}

void MergeSort(int * A, unsigned int p, unsigned int r){
	if (p >= r)
		return;

	unsigned int q = (p + r) / 2;

	MergeSort(A, p, q);
	MergeSort(A, q + 1, r);
	Merge(A, p, q, r);
}

/*
	int * array = new int[n];
	...
	MergeSort(array, 0, n-1);
	delete[] array;
*/