fork download
copy 
  1. /**
  2.  * Merge Sort using N/2 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. using namespace std;
  12.  
  13. template <class T> void swap ( T& a, T& b ) {
  14.   T c(a); a=b; b=c;
  15. }
  16.  
  17.  
  18. /* Sort the given array in the range [iFrom,iTo), using a temporary storage starting at iTemp  */
  19. template <class Iterator> void merge_sort(Iterator iFrom, Iterator iTo, Iterator iTemp) {
  20.   if (iTo <= iFrom+1)
  21.     return;
  22.  
  23.   // recursively sort each half seperately:
  24.   size_t diff = (iTo-iFrom);
  25.   //cout << "merge_sort " << diff << " elements: " << *iFrom << ".." << *(iTo-1) << endl;
  26.   Iterator iMiddle = iFrom+diff/2;
  27.  
  28.   merge_sort(iFrom, iMiddle, iTemp);
  29.   merge_sort(iMiddle, iTo, iTemp);
  30.  
  31.  
  32.   // merge the two halves using the temporary storage:
  33.  
  34.   /// a. move the smaller array to the temporary storage:
  35.   Iterator iLeft, iOutput;
  36.   for (iLeft=iFrom, iOutput=iTemp; iLeft<iMiddle; ++iLeft, ++iOutput)
  37.     *iOutput = *iLeft;
  38.   Iterator iTempEnd = iOutput;
  39.  
  40.   /// b. merge the smaller array from the temp storage to the main array:
  41.   Iterator iRight;
  42.   for (iOutput=iFrom, iLeft=iTemp, iRight=iMiddle; iLeft<iTempEnd && iRight<iTo;) {
  43.     //cout << "comparing " << *iLeft << " and " << *iRight;
  44.     if (*iLeft <= *iRight) {
  45.       *iOutput = *iLeft;
  46.       ++iLeft;
  47.     } else {
  48.       *iOutput = *iRight;
  49.       ++iRight;
  50.     }
  51.     //cout << "; putting " << *iOutput << endl;
  52.     ++iOutput;
  53.   }
  54.  
  55.   for (; iLeft<iTempEnd; ) {
  56.     *iOutput = *iLeft;
  57.     ++iLeft;
  58.     ++iOutput;
  59.   }
  60.  
  61.   for (; iRight<iTo; ) {
  62.     *iOutput = *iRight;
  63.     ++iRight;
  64.     ++iOutput;
  65.   }
  66. }
  67.  
  68.  
  69. template <class T> void merge_sort(vector<T>& array) {
  70.   vector<T> temp(array.size()/2);  // temporary vector for merging
  71.   merge_sort(array.begin(), array.end(), temp.begin());
  72. }
  73.  
  74.  
  75.  
  76. #include <stdlib.h>
  77. #include <time.h>
  78. int main() {
  79.   srand(time(NULL)); 
  80.   int num;
  81.   vector<int> numbers;
  82.   while (1) {
  83.     cin >> num;
  84.     if (cin.eof()) break;
  85.     if (num==0)  // 0 means "choose at random"
  86.       num = rand()%100;
  87.     numbers.push_back(num);
  88.   }
  89.  
  90.   cout << endl << "before sort: ";
  91.   for (size_t i=0; i<numbers.size(); ++i) cout << numbers[i] << " ";
  92.   merge_sort(numbers);
  93.   cout << endl << "after sort: ";
  94.   for (size_t i=0; i<numbers.size(); ++i) cout << numbers[i] << " ";
  95. }
  96.  
Success #stdin #stdout 0s 2864KB
comments (?)
stdin
copy 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
stdout
copy 
before sort: 63 86 17 3 0 61 42 49 44 21 5 67 32 46 93 25 80 
after sort: 0 3 5 17 21 25 32 42 44 46 49 61 63 67 80 86 93
https://ideone.com/sCh8v
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!