Non-recursive Merge Sort (cpp_merge_sort.cc)
================================================================================最好时间复杂度 O(nlogn)平均时间复杂度 O(nlogn)最坏时间复杂度 O(nlogn)空间复杂度 O(n)是否稳定 是 Non-recursive Merge Sort是归并排序的非递归(自底向上归并)实现，将序列视为长度为s的有序序列集合(初始时s=1)，然后将有序序列两两进行Merge操作，得到长度为2s的有序序列集合，重复操作直到序列中只剩下一个有序序列时排序结束。 Non-recursive Merge Sort在所有测试的算法中速度仅次于Quick Sort，在需要排序稳定性或者O(nlogn)最坏情况时是Quick Sort的一个很好的替代，但所需O(n)的空间复杂度是对算法速度和适用范围一个严重的制约。SGI-STL库中std::stable_sort()的内部实现就是Non-recursive Merge Sort。1 #include2 #include 3 #include 4 5 static unsigned int set_times = 0; 6 static unsigned int cmp_times = 0; 7 8 template void setval(item_type& item1, item_type& item2) { 9 set_times += 1; 10 item1 = item2; 11 return; 12 } 13 14 template int compare(item_type& item1, item_type& item2) { 15 cmp_times += 1; 16 return item1 < item2; 17 } 18 19 template void swap(item_type& item1, item_type& item2) { 20 item_type item3; 21 22 setval(item3, item1); 23 setval(item1, item2); 24 setval(item2, item3); 25 return; 26 } 27 28 template void ncmerge_sort(item_type* array, int size) { 29 int step_width; 30 int ins_pos; 31 int l; 32 int m; 33 int r; 34 int pos1; 35 int pos2; 36 item_type* temp_array = new item_type[size]; 37 38 for(step_width = 2; step_width < size * 2; step_width *= 2) { 39 for(l = 0; l + step_width / 2 < size; l += step_width) { 40 m = l + step_width / 2; 41 r = m + step_width / 2 < size ? m + step_width / 2 : size; 42 43 pos1 = l; 44 pos2 = m; 45 ins_pos = 0; 46 while(pos1 < m && pos2 < r) { 47 if(compare(array[pos2], array[pos1])) { 48 setval(temp_array[ins_pos++], array[pos2++]); 49 } else { 50 setval(temp_array[ins_pos++], array[pos1++]); 51 } 52 } 53 while(pos1 < m) setval(temp_array[ins_pos++], array[pos1++]); 54 while(pos2 < r) setval(temp_array[ins_pos++], array[pos2++]); 55 while(ins_pos > 0) { 56 setval(array[--r], temp_array[--ins_pos]); 57 } 58 } 59 } 60 delete[] temp_array; 61 return; 62 } 63 64 int main(int argc, char** argv) { 65 int capacity = 0; 66 int size = 0; 67 int i; 68 clock_t clock1; 69 clock_t clock2; 70 double data; 71 double* array = NULL; 72 73 // generate randomized test case 74 while(scanf("%lf", &data) == 1) { 75 if(size == capacity) { 76 capacity = (size + 1) * 2; 77 array = (double*)realloc(array, capacity * sizeof(double)); 78 } 79 array[size++] = data; 80 } 81 82 // sort 83 clock1 = clock(); 84 ncmerge_sort(array, size); 85 clock2 = clock(); 86 87 // output test result 88 fprintf(stderr, "ncmerge_sort:\t"); 89 fprintf(stderr, "time %.2lf\t", (double)(clock2 - clock1) / CLOCKS_PER_SEC); 90 fprintf(stderr, "cmp_per_elem %.2lf\t", (double)cmp_times / size); 91 fprintf(stderr, "set_per_elem %.2lf\n", (double)set_times / size); 92 for(i = 0; i < size; i++) { 93 fprintf(stdout, "%lf\n", array[i]); 94 } 95 free(array); 96 return 0; 97 }