forked from leo000leo/Algorithm
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathmerge_sort.h
More file actions
88 lines (73 loc) · 2.48 KB
/
Copy pathmerge_sort.h
File metadata and controls
88 lines (73 loc) · 2.48 KB
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
//
// merge_sort
// Algorithm
//
// Created by dtysky on 16/9/13.
// Copyright © 2016 [email protected]. All rights reserved.
//
#ifndef ALGORITHM_MERGE_SORT_H
#define ALGORITHM_MERGE_SORT_H
#include <cstdio>
#include <vector>
namespace my_algorithm {
using std::vector;
// time: O(n * log(n))
// space: O(Pn)
template <typename T>
void mergeSort(vector<T>& t_vector, const bool reverse = false) {
auto size = t_vector.size();
size_t step = 1;
while (step < size) {
auto tmp = vector<T>();
for (size_t begin = 0; begin < size; begin += 2 * step) {
auto middle = (begin + step) > size ? size : (begin + step);
auto end = (middle + step) > size ? size : (middle + step);
if (middle == end) {
for (auto i = begin; i < end; i++) {
tmp.push_back(t_vector[i]);
}
continue;
}
if (reverse && t_vector[middle - 1] > t_vector[middle]) {
for (auto i = begin; i < end; i++) {
tmp.push_back(t_vector[i]);
}
continue;
}
if (!reverse && t_vector[middle - 1] < t_vector[middle]) {
for (auto i = begin; i < end; i++) {
tmp.push_back(t_vector[i]);
}
continue;
}
auto i1 = begin;
auto i2 = middle;
while (i1 < middle || i2 < end) {
if (i1 == middle) {
tmp.push_back(t_vector[i2]);
i2++;
}
else if (i2 == end) {
tmp.push_back(t_vector[i1]);
i1++;
}
else if (reverse && t_vector[i1] > t_vector[i2]) {
tmp.push_back(t_vector[i1]);
i1++;
}
else if (!reverse && t_vector[i1] < t_vector[i2]) {
tmp.push_back(t_vector[i1]);
i1++;
}
else {
tmp.push_back(t_vector[i2]);
i2++;
}
}
}
t_vector = tmp;
step *= 2;
}
}
}
#endif //ALGORITHM_MERGE_SORT_H