fork download
copy 
  1. #include <iostream>
  2. #include <iterator>
  3. #include <algorithm>
  4. #include <vector>
  5. using namespace std;
  6.  
  7. // general mergesort algorithm
  8. template <typename Iterator>
  9. void mergesort(Iterator first, Iterator last)
  10. {
  11.     typedef typename std::iterator_traits<Iterator>::value_type value_type;
  12.  
  13.     size_t d = std::distance(first, last);
  14.     size_t n = d/2;
  15.     if (n == 0)
  16.         return;
  17.  
  18.     // invoke recursion on the submerges
  19.     if (n > 1)
  20.         mergesort(first, first + n);
  21.     if (d > 1)
  22.         mergesort(first + n, last);
  23.  
  24.     // create merge-buffer
  25.     std::vector<value_type> mrg;
  26.     mrg.reserve(d);
  27.  
  28.     // and merge into it.
  29.     std::merge(first, first+n, first+n, last, back_inserter(mrg));
  30.     std::copy(mrg.begin(), mrg.end(), first);
  31. }
  32.  
  33. // front-loader for static arrays
  34. template<typename Item, size_t N>
  35. void mergesort(Item (&ar)[N])
  36. {
  37.     mergesort(std::begin(ar), std::end(ar));
  38. }
  39.  
  40. int main()
  41. {
  42.     srand((unsigned)time(0));
  43.     vector<int> data;
  44.  
  45.     // fill a vector with random junk.
  46.     generate_n(back_inserter(data), 15, []() { return std::rand() % 99+1;});
  47.     copy(data.begin(), data.end(), ostream_iterator<int>(cout, " "));
  48.     cout << endl;
  49.  
  50.     mergesort(data.begin(), data.end());
  51.     copy(data.begin(), data.end(), ostream_iterator<int>(cout, " "));
  52.     cout << endl;
  53.     return 0;
  54. }
Success #stdin #stdout 0s 3032KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
11 60 52 25 28 37 56 88 15 52 70 56 51 12 24 
11 12 15 24 25 28 37 51 52 52 56 56 60 70 88
https://ideone.com/bPT2HK
language:
C++14 (gcc 8.3)
created:
12 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!