fork download
copy 
  1. /**
  2. * Merge Sort using O(1) temporary storage.
  3. * @see http://e...content-available-to-author-only...a.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
comments (?)
stdin
copy 


			

					
			
			

				
	
		
		
	
		
		 stdout
					

				
				 copy
			

			
	

		
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 


	

		
	 
	
	
			

					
			
			
			
			
			
			
			
			

			
			
			
		

	
		
		

			

			                        







			
			

				

	
					
					 https://ideone.com/oU5aF
					
					
					
					
					

												

												
						
						

					

					
					
					

						
language:

						
C++ (gcc 8.3)

					

					

						
created:
								
						
13 years ago

					

					

						
visibility:

						

							 public																												
							
							

								
							

						

					

										
										

					
					 Share or Embed source code
					
					
					
					

						
						
						
						
						
						
						
					

					
						
	
	
	
	
					
					
					
					
					 
					
					
					
					 
					
					
					
					
					
					

					

					

					
						
					

					


	
Discover > Sphere Engine API

	
The brand new service which powers Ideone!

	
	
Discover > IDE Widget

    
Widget for compiling and running the source code in a web browser!