-
Notifications
You must be signed in to change notification settings - Fork 0
/
timSort.h
51 lines (47 loc) · 1.51 KB
/
timSort.h
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
#include "inplaceMerge.h"
#include "merges.h"
#include "checks.h"
#include "updates.h"
enum MonotonyType {
undefined,
decreasing,
nonDecreasing
};
template <class Iter, class Compare>
void timSort(Iter begin, Iter end, Compare cmp, const ITimSortParams ¶ms) {
int n = end - begin;
if (n == 1) {
return;
}
int length = params.minRun(n);
vector<pair<Iter, int> > runs;
int curLen = 1;
int pos = 0;
MonotonyType monotony = undefined;
while (pos < n) {
if (pos + 1 == n) {
checkIfLast(pos, n, monotony, curLen, begin, cmp, runs, params);
break;
}
if (monotony == undefined) {
checkIfUndefined(pos, n, monotony, curLen, begin, cmp, runs, params);
} else if (monotony == decreasing) {
checkIfDecreasing(pos, n, monotony, curLen, length, begin, cmp, runs, params);
} else if (monotony == nonDecreasing) {
checkIfNonDecreasing(pos, n, monotony, curLen, length, begin, cmp, runs, params);
}
++pos;
}
mergeAllRuns(runs, cmp, params);
assert(runs.size() == 1);
}
template <class Iter, class Compare>
void timSort(Iter begin, Iter end, Compare cmp) {
timSort(begin, end, cmp, TimSortParams());
}
template <class Iter>
void timSort(Iter begin, Iter end) {
typedef typename std::iterator_traits<Iter>::value_type value_type;
std::less<value_type> cmp = std::less<value_type>();
timSort(begin, end, cmp, TimSortParams());
}