fork download 
  1. #include <iostream>
  2. #include <iterator>
  3. #include <algorithm>
  4. #include <vector>
  5. #include <iterator>
  6. using namespace std;
  7.  
  8. template <typename Iterator>
  9.  
  10. // general mergesort algorithm
  11. void mergesort(Iterator first, Iterator last)
  12. {
  13.     typedef typename std::iterator_traits<Iterator>::value_type value_type;
  14.  
  15.     size_t d = std::distance(first, last);
  16.     size_t n = d/2;
  17.     if (n == 0)
  18.         return;
  19.  
  20.     // invoke recursion on the submerges
  21.     if (n > 1)
  22.         mergesort(first, first + n);
  23.     if (d > 1)
  24.         mergesort(first + n, last);
  25.  
  26.     // and in-place merge back
  27.     std::inplace_merge(first, first+n, last);
  28. }
  29.  
  30. int main()
  31. {
  32.     srand((unsigned)time(0));
  33.     vector<int> data;
  34.  
  35.     // fill a vector with random junk.
  36.     // fill a vector with random junk.
  37.     generate_n(back_inserter(data), 15, []() { return std::rand() % 99+1;});
  38.     copy(data.begin(), data.end(), ostream_iterator<int>(cout, " "));
  39.     cout << endl;
  40.  
  41.     mergesort(data.begin(), data.end());
  42.     copy(data.begin(), data.end(), ostream_iterator<int>(cout, " "));
  43.     cout << endl;
  44.  
  45.     return 0;
  46. }
  47.  
Success #stdin #stdout 0s 3032KB
comments (?)
stdin 
Standard input is empty
stdout 
31 25 41 45 73 34 60 65 5 63 44 11 9 84 65 
5 9 11 25 31 34 41 44 45 60 63 65 65 73 84
https://ideone.com/Ayt5jq
language:
C++14 (gcc 8.3)
created:
12 years ago
visibility:
secret

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!