fork download
copy 
  1.  
  2. #include <iostream>
  3. #include <vector>
  4. #include <list>
  5. #include <algorithm>
  6. #include <iterator>
  7. #include <type_traits>
  8.  
  9.  
  10. template<typename Iterator>
  11. void merge_sort(Iterator begin, Iterator end)
  12. {
  13.   static_assert( std::is_same<
  14.                    typename std::iterator_traits<Iterator>::iterator_category, 
  15.                    std::random_access_iterator_tag
  16.                  >::value, "merge_sort only likes random-access iterators" );
  17.   const auto n = std::distance(begin, end);
  18.   const auto p = n / 2;
  19.  
  20.   if(n < 2)
  21.     return;
  22.  
  23.   merge_sort(begin, begin + p);
  24.   merge_sort(begin + p, end);
  25.  
  26.   std::inplace_merge(begin, begin + p, end);
  27. }
  28.  
  29. template<typename T>
  30. void merge_sort(T& v)
  31. {
  32.   using std::begin;
  33.   using std::end;
  34.   merge_sort(begin(v), end(v));
  35. }
  36.  
  37. int main()
  38. {
  39.   int v1[] = {6,5,4,3,2,1};
  40.   std::vector<int> v2 = {6,5,4,3,2,1};
  41.   // std::list<int> v = {6,5,4,3,2,1};
  42.  
  43.   merge_sort(v1);
  44.   for(auto const& x : v1)
  45.     std::cout << x << " ";
  46.   std::cout << std::endl;
  47.  
  48.   merge_sort(v2);
  49.   for(auto const& x : v2)
  50.     std::cout << x << " ";
  51.   std::cout << std::endl;
  52.  
  53.   return 0;
  54. }
Success #stdin #stdout 0s 3036KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1 2 3 4 5 6 
1 2 3 4 5 6
https://ideone.com/fvu57s
language:
C++14 (gcc 8.3)
created:
11 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!