fork download
  1. /**
  2. * Merge Sort using O(1) temporary storage.
  3. * @see http://en.wikipedia.org/wiki/Merge_sort#Analysis
  4. *
  5. * Author: Erel Segal
  6. * Created: 2010-10-17
  7. */
  8.  
  9. #include <vector>
  10. #include <iostream>
  11. #include <stdlib.h>
  12. using namespace std;
  13.  
  14.  
  15. /*
  16.   FUNCTIONS FOR DEBUGGING
  17. */
  18.  
  19. template <class Iterator> ostream& print (ostream& out, Iterator iFrom, Iterator iTo) {
  20. for (; iFrom!=iTo; ++iFrom) out << *iFrom << " ";
  21. return (out << endl);
  22. }
  23.  
  24. template <class Iterator> bool assertSorted(Iterator iFrom, Iterator iTo) {
  25. for (; iFrom<iTo-1; ++iFrom) {
  26. if (*iFrom > *(iFrom+1)) {
  27. cerr << "array is out of order: " << *iFrom << " > " << *(iFrom+1) << endl;
  28. return false;
  29. }
  30. }
  31. return true;
  32. }
  33.  
  34. int* randomArray(size_t size) {
  35. int* a = new int[size];
  36. for (size_t i=0; i<size; ++i)
  37. a[i] = rand()%100;
  38. return a;
  39. }
  40.  
  41.  
  42. template <class T> void swap ( T& a, T& b ) { T c(a); a=b; b=c; }
  43.  
  44. size_t gcd(size_t n, size_t m) {return m==0?n:gcd(m,n%m);}
  45.  
  46.  
  47.  
  48. /**
  49.  * Rotate the combined range [iFrom1, iTo1)[iFrom2, iTo2) such that the elements [iFrom1,iTo1) will be at the end.
  50.  */
  51. template <class Iterator> void rotateRanges (Iterator iFrom1, Iterator iTo1, Iterator iFrom2, Iterator iTo2) {
  52. size_t size1 = iTo1-iFrom1, size2 = iTo2-iFrom2, totalSize = size1+size2;
  53. size_t gcd12 = gcd(size1,size2);
  54. size_t offset1start, offset1, offset2;
  55. Iterator iter1, iter2;
  56. typename std::iterator_traits<Iterator>::value_type temp; // the O(1) temporary storage
  57. for (offset1start=0; offset1start<gcd12; ++offset1start) {
  58. temp = *(iFrom1+offset1start);
  59. for (offset1=offset1start;;) {
  60. iter1 = (offset1<size1? iFrom1+offset1: iFrom2+(offset1-size1));
  61. offset2 = (offset1+size1)%totalSize;
  62. iter2 = (offset2<size1? iFrom1+offset2: iFrom2+(offset2-size1));
  63. if (offset2==offset1start) break; // completed a cycle
  64. *iter1 = *iter2;
  65. offset1 = offset2;
  66. }
  67. *iter1 = temp;
  68. }
  69. }
  70.  
  71. /**
  72.  * Merge the two sorted ranges using the given temporary storage (O(1) storage).
  73.  * PRECONDITION: [iFrom1, iTo1) are in ascending order, [iFrom2, iTo2) are in ascending order
  74.  * POSTCONDITION: [iFrom1, iTo1) are in ascending order AND <= [iFrom2, iTo2), who are also in ascending order
  75.  */
  76. template <class Iterator> void mergeRanges (Iterator iFrom1, Iterator iTo1, Iterator iFrom2, Iterator iTo2) {
  77. // HERE: [iFrom1, iTo1) are in ascending order
  78. // HERE: [iFrom2, iTo2) are in ascending order
  79.  
  80. Iterator i1 = iFrom1;
  81. // HERE: [iFrom1, i1) are in ascending order and < [iFrom2, iTo2) [empty range]
  82.  
  83. for (;;) {
  84. while (*i1 < *iFrom2 && i1 < iTo1) {
  85. ++i1;
  86. }
  87. // HERE: [iFrom1,i1) are in ascending order and < [iFrom2,iTo2)
  88.  
  89. if (i1 == iTo1) {
  90. // HERE: [iFrom1, iTo1) are in ascending order and < [iFrom2, iTo2)
  91. return; // POSTCONDITION satisfied.
  92. }
  93.  
  94. // HERE: [i1] >= [iFrom2]
  95.  
  96. Iterator j2 = iFrom2;
  97. // HERE: [iFrom2,j2) are in ascending order and <= [i1,iTo1) [empty range]
  98. while (*j2 <= *i1 && j2 < iTo2) {
  99. ++j2;
  100. }
  101. // HERE: [iFrom2,j2) are in ascending order and <= [i1,iTo1)
  102.  
  103. if (j2 == iTo2) {
  104. // HERE: [iFrom2,iTo2) <= [i1,iTo1)
  105. rotateRanges(i1, iTo1, iFrom2, iTo2);
  106. // HERE: [i1,iTo1) <= [iFrom2,iTo2) and in ascending order.
  107. // Since [iFrom1,i1) are also in ascending order, it follows that:
  108. // [iFrom1,iTo1) <= [iFrom2,iTo2) and in ascending order.
  109. return; // POSTCONDITION satisfied.
  110. }
  111.  
  112. // HERE: [j2] > [i1]
  113.  
  114. Iterator j1 = i1;
  115. // HERE: [iFrom2,j2) <= [i1,j1) < [j2] [empty range]
  116.  
  117. while (*j1 < *j2 && j1 < iTo1) {
  118. ++j1;
  119. }
  120. // HERE: [iFrom2,j2) <= [i1,j1) < [j2]
  121.  
  122. rotateRanges(i1, j1, iFrom2, j2);
  123. // HERE: [i1,j1) <= [iFrom2,j2) < [j2]
  124. // HERE: [iFrom1,j1) are in ascending order and <= [iFrom2,iTo2)
  125.  
  126. i1 = j1;
  127. // HERE: [iFrom1,i1) are in ascending order and <= [iFrom2,iTo2)
  128. }
  129. }
  130.  
  131.  
  132. /* Sort the given array in the range [iFrom,iTo), using O(1) temporary storage */
  133. template <class Iterator> void merge_sort(Iterator iFrom, Iterator iTo, string prefix="") {
  134. if (iTo <= iFrom+1)
  135. return;
  136.  
  137. // recursively sort each half seperately:
  138. size_t diff = (iTo-iFrom);
  139. cout << prefix << "merge_sort " << diff << " elements: "; print(cout, iFrom, iTo);
  140. Iterator iMiddle = iFrom+diff/2;
  141.  
  142. merge_sort(iFrom, iMiddle, prefix+" ");
  143. merge_sort(iMiddle, iTo, prefix+" ");
  144.  
  145. mergeRanges(iFrom, iMiddle, iMiddle, iTo);
  146.  
  147. cout << prefix << "sorted " << diff << " elements: "; print(cout, iFrom, iTo);
  148. if (!assertSorted(iFrom, iTo))
  149. exit(1);
  150. }
  151.  
  152.  
  153. #include <stdlib.h>
  154. #include <time.h>
  155. int main() {
  156. {
  157. cout << "Demonstrating rotateRanges: " << endl;
  158. int a[] = {1,2, 101,102,103,104};
  159. int b[] = {3,4,5,5,6,7,8,9};
  160. cout << "before rotate: " << endl;
  161. print (cout, a, a+6);
  162. print (cout, b, b+8);
  163. rotateRanges(a+2, a+6, b+0, b+8);
  164. cout << "after rotate of a[2,6) with b[0,8) : " << endl;
  165. print (cout, a, a+6);
  166. print (cout, b, b+8);
  167. cout << endl;
  168.  
  169. int c[] = {1,2, 101,102,103,104};
  170. int d[] = {3,4};
  171. cout << "before rotate: " << endl;
  172. print (cout, c, c+6);
  173. print (cout, d, d+2);
  174. rotateRanges(c+2, c+6, d+0, d+2);
  175. cout << "after rotate of c[2,6) with d[0,2): " << endl;
  176. print (cout, c, c+6);
  177. print (cout, d, d+2);
  178. cout << endl << endl;
  179. }
  180.  
  181. {
  182. cout << "Demonstrating mergeRanges: " << endl;
  183. int a[] = {3,8};
  184. int b[] = {2,4,9};
  185. cout << "before merge: " << endl;
  186. print (cout, a, a+2);
  187. print (cout, b, b+3);
  188. mergeRanges(a, a+2, b, b+3);
  189. cout << "after merge: " << endl;
  190. print (cout, a, a+2);
  191. print (cout, b, b+3);
  192. cout << endl;
  193. }
  194. {
  195. int c[] = {15,77,83,86,93};
  196. int d[] = {21,35,86,86,92};
  197. cout << "before merge: " << endl;
  198. print (cout, c, c+5);
  199. print (cout, d, d+5);
  200. mergeRanges(c, c+5, d, d+5);
  201. cout << "after merge: " << endl;
  202. print (cout, c, c+5);
  203. print (cout, d, d+5);
  204. cout << endl << endl;
  205. }
  206. {
  207. int c[] = {6,7,8,9,10};
  208. int d[] = {1,2,3,4,5};
  209. cout << "before merge: " << endl;
  210. print (cout, c, c+5);
  211. print (cout, d, d+5);
  212. mergeRanges(c, c+5, d, d+5);
  213. cout << "after merge: " << endl;
  214. print (cout, c, c+5);
  215. print (cout, d, d+5);
  216. cout << endl << endl;
  217. }
  218.  
  219. cout << "Demonstrating merge_sort: " << endl;
  220. size_t size=30;
  221. int* numbers = randomArray(size);
  222. merge_sort(numbers, numbers+size);
  223. assertSorted(numbers, numbers+size);
  224. }
  225.  
Success #stdin #stdout 0s 2864KB
stdin
stdout
Demonstrating rotateRanges: 
before rotate: 
1 2 101 102 103 104 
3 4 5 5 6 7 8 9 
after rotate of a[2,6) with b[0,8) : 
1 2 3 4 5 5 
6 7 8 9 101 102 103 104 

before rotate: 
1 2 101 102 103 104 
3 4 
after rotate of c[2,6) with d[0,2): 
1 2 3 4 101 102 
103 104 


Demonstrating mergeRanges: 
before merge: 
3 8 
2 4 9 
after merge: 
2 3 
4 8 9 

before merge: 
15 77 83 86 93 
21 35 86 86 92 
after merge: 
15 21 35 77 83 
86 86 86 92 93 


before merge: 
6 7 8 9 10 
1 2 3 4 5 
after merge: 
1 2 3 4 5 
6 7 8 9 10 


Demonstrating merge_sort: 
merge_sort 30 elements: 83 86 77 15 93 35 86 92 49 21 62 27 90 59 63 26 40 26 72 36 11 68 67 29 82 30 62 23 67 35 
 merge_sort 15 elements: 83 86 77 15 93 35 86 92 49 21 62 27 90 59 63 
  merge_sort 7 elements: 83 86 77 15 93 35 86 
   merge_sort 3 elements: 83 86 77 
    merge_sort 2 elements: 86 77 
    sorted 2 elements: 77 86 
   sorted 3 elements: 77 83 86 
   merge_sort 4 elements: 15 93 35 86 
    merge_sort 2 elements: 15 93 
    sorted 2 elements: 15 93 
    merge_sort 2 elements: 35 86 
    sorted 2 elements: 35 86 
   sorted 4 elements: 15 35 86 93 
  sorted 7 elements: 15 35 77 83 86 86 93 
  merge_sort 8 elements: 92 49 21 62 27 90 59 63 
   merge_sort 4 elements: 92 49 21 62 
    merge_sort 2 elements: 92 49 
    sorted 2 elements: 49 92 
    merge_sort 2 elements: 21 62 
    sorted 2 elements: 21 62 
   sorted 4 elements: 21 49 62 92 
   merge_sort 4 elements: 27 90 59 63 
    merge_sort 2 elements: 27 90 
    sorted 2 elements: 27 90 
    merge_sort 2 elements: 59 63 
    sorted 2 elements: 59 63 
   sorted 4 elements: 27 59 63 90 
  sorted 8 elements: 21 27 49 59 62 63 90 92 
 sorted 15 elements: 15 21 27 35 49 59 62 63 77 83 86 86 90 92 93 
 merge_sort 15 elements: 26 40 26 72 36 11 68 67 29 82 30 62 23 67 35 
  merge_sort 7 elements: 26 40 26 72 36 11 68 
   merge_sort 3 elements: 26 40 26 
    merge_sort 2 elements: 40 26 
    sorted 2 elements: 26 40 
   sorted 3 elements: 26 26 40 
   merge_sort 4 elements: 72 36 11 68 
    merge_sort 2 elements: 72 36 
    sorted 2 elements: 36 72 
    merge_sort 2 elements: 11 68 
    sorted 2 elements: 11 68 
   sorted 4 elements: 11 36 68 72 
  sorted 7 elements: 11 26 26 36 40 68 72 
  merge_sort 8 elements: 67 29 82 30 62 23 67 35 
   merge_sort 4 elements: 67 29 82 30 
    merge_sort 2 elements: 67 29 
    sorted 2 elements: 29 67 
    merge_sort 2 elements: 82 30 
    sorted 2 elements: 30 82 
   sorted 4 elements: 29 30 67 82 
   merge_sort 4 elements: 62 23 67 35 
    merge_sort 2 elements: 62 23 
    sorted 2 elements: 23 62 
    merge_sort 2 elements: 67 35 
    sorted 2 elements: 35 67 
   sorted 4 elements: 23 35 62 67 
  sorted 8 elements: 23 29 30 35 62 67 67 82 
 sorted 15 elements: 11 23 26 26 29 30 35 36 40 62 67 67 68 72 82 
sorted 30 elements: 11 15 21 23 26 26 27 29 30 35 35 36 40 49 59 62 62 63 67 67 68 72 77 82 83 86 86 90 92 93