Non-recursive Merge Sort (cpp_merge_sort.cc)
================================================================================
最好时间复杂度 O(nlogn)
平均时间复杂度 O(nlogn)
最坏时间复杂度 O(nlogn)
空间复杂度 O(1)
是否稳定 是
Inplace Merge Sort是自底向上归并排序的原地实现，通过一个精巧的原地Merge操作将归并排序的O(n)空间减小至O(1)。
原地Merge操作基于大量的Swap，所以该算法的时间效率并不高。同时原地Merge操作也破坏了排序算法的稳定性，使得该算法在主要理论参数上和Heap Sort相同，但实际速度要慢于Heap Sort，所以并不是一个实用的算法。
1 #include <cstdio>
2 #include <cstdlib>
3 #include <cstring>
4 #include <ctime>
5 #include <cmath>
6
7 static unsigned int set_times = 0;
8 static unsigned int cmp_times = 0;
9
10 template<typename item_type> void setval(item_type& item1, item_type& item2) {
11 set_times += 1;
12 item1 = item2;
13 return;
14 }
15
16 template<typename item_type> int compare(item_type& item1, item_type& item2) {
17 cmp_times += 1;
18 return item1 < item2;
19 }
20
21 template<typename item_type> void swap(item_type& item1, item_type& item2) {
22 item_type item3;
23
24 setval(item3, item1);
25 setval(item1, item2);
26 setval(item2, item3);
27 return;
28 }
29
30 template<typename item_type> void ipmerge_insert_sort(item_type* array, int size) {
31 int i;
32 int j;
33 item_type tempitem;
34
35 for(i = 1; i < size; i++) {
36 setval(tempitem, array[i]);
37 for(j = i - 1; j >= 0 && compare(tempitem, array[j]); j -= 1) {
38 setval(array[j + 1], array[j]);
39 }
40 setval(array[j + 1], tempitem);
41 }
42 return;
43 }
44
45 template<typename item_type> void ipmerge_merge_aux(item_type* array, int size, int mid, item_type* aux) {
46 int ins_pos;
47 int pos1;
48 int pos2;
49
50 if(mid <= size / 2) {
51 for(pos1 = 0; pos1 < mid; pos1++) {
52 swap(array[pos1], aux[pos1]);
53 }
54
55 pos1 = mid;
56 pos2 = 0;
57 ins_pos = 0;
58 while(pos2 < mid) {
59 if(pos1 < size && compare(array[pos1], aux[pos2])) {
60 swap(array[ins_pos++], array[pos1++]);
61 } else {
62 swap(array[ins_pos++], aux[pos2++]);
63 }
64 }
65 } else {
66 for(pos1 = mid; pos1 < size; pos1++) {
67 swap(array[pos1], aux[pos1 - mid]);
68 }
69
70 pos1 = mid - 1;
71 pos2 = size - mid - 1;
72 ins_pos = size - 1;
73 while(pos2 >= 0) {
74 if(pos1 >= 0 && compare(aux[pos2], array[pos1])) {
75 swap(array[ins_pos--], array[pos1--]);
76 } else {
77 swap(array[ins_pos--], aux[pos2--]);
78 }
79 }
80 }
81 return;
82 }
83
84 template<typename item_type> void ipmerge_merge(item_type* array, int size, int mid) {
85 int n;
86 int m;
87 int s;
88 int i;
89 int current_block;
90 int min_block;
91
92 if(size > 16) {
93 n = sqrt(size);
94 m = (size + n - 1) / n - 2;
95 s = size - m * n;
96
97 // [z1][z2]...[zmid]...[zm][zm+1][zm+2]
98 if(mid < m * n) {
99 for(i = 0; i < n; i++) {
100 swap(array[i + (mid / n) * n], array[i + m * n]);
101 }
102 }
103
104 // [z1][z2]...[zm+1]...[zm][zmid][zm+2]
105 for(current_block = 0; current_block < m; current_block++) {
106 for(min_block = current_block, i = current_block + 1; i < m; i++) {
107 if(compare(array[i * n], array[min_block * n])
108 || (!compare(array[min_block * n], array[i * n])
109 && compare(array[i * n + m - 1], array[min_block * n + m - 1]))) {
110 min_block = i;
111 }
112 }
113 if(min_block != current_block) {
114 for(i = 0; i < n; i++) {
115 swap(array[i + current_block * n], array[i + min_block * n]);
116 }
117 }
118 }
119
120 // [z1'][z2']...[zm'][s]
121 for(i = 0; i < m - 1; i++) {
122 ipmerge_merge_aux(array + i * n, n * 2, n, array + m * n);
123 }
124
125 // [r][s]
126 ipmerge_insert_sort(array + size - 2 * s, 2 * s);
127 ipmerge_merge_aux(array, m * n, m * n - s, array + m * n);
128 ipmerge_insert_sort(array + m * n, s);
129 } else {
130 ipmerge_insert_sort(array, size);
131 }
132 return;
133 }
134
135 template<typename item_type> void ipmerge_sort(item_type* array, int size) {
136 int step_width;
137 int l;
138 int m;
139 int r;
140
141 for(step_width = 2; step_width < size * 2; step_width *= 2) {
142 for(l = 0; l + step_width / 2 < size; l += step_width) {
143 m = l + step_width / 2;
144 r = m + step_width / 2 < size ? m + step_width / 2 : size;
145 ipmerge_merge(array + l, r - l, m - l);
146 }
147 }
148 return;
149 }
150
151 int main(int argc, char** argv) {
152 int capacity = 0;
153 int size = 0;
154 int i;
155 clock_t clock1;
156 clock_t clock2;
157 double data;
158 double* array = NULL;
159
160 // generate randomized test case
161 while(scanf("%lf", &data) == 1) {
162 if(size == capacity) {
163 capacity = (size + 1) * 2;
164 array = (double*)realloc(array, capacity * sizeof(double));
165 }
166 array[size++] = data;
167 }
168
169 // sort
170 clock1 = clock();
171 ipmerge_sort(array, size);
172 clock2 = clock();
173
174 // output test result
175 fprintf(stderr, "ipmerge_sort:\t");
176 fprintf(stderr, "time %.2lf\t", (double)(clock2 - clock1) / CLOCKS_PER_SEC);
177 fprintf(stderr, "cmp_per_elem %.2lf\t", (double)cmp_times / size);
178 fprintf(stderr, "set_per_elem %.2lf\n", (double)set_times / size);
179 for(i = 0; i < size; i++) {
180 fprintf(stdout, "%lf\n", array[i]);
181 }
182 free(array);
183 return 0;
184 }