fork download 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. void mergesort(std::vector<int>& A, int l, int r);
  6.  
  7. void tmerge(std::vector<int>& A, int l, int m, int r);
  8.  
  9.  
  10. void mergesort(std::vector<int>& A, int l, int r) {
  11.  
  12.     if(l < r) {
  13.  
  14.         int m = l + (r - l) / 2;
  15.  
  16.         mergesort(A, l, m);
  17.  
  18.         mergesort(A, m+1, r);
  19.  
  20.         tmerge(A, l, m, r);
  21.  
  22.     }
  23. }
  24.  
  25. void tmerge(std::vector<int>& A, int l, int m, int r) {
  26.    std::vector<int> L;
  27.    std::vector<int> R;
  28.    int n1 = m - l + 1;
  29.    int n2 =  r - m;
  30.    if(n1 > 0)
  31.    {
  32.        for(int i=0; i<n1; i++) L.push_back(0);
  33.        std::copy(A.begin() + l, A.begin() + (l+n1), L.begin());
  34.    }
  35.    if(n2 > 0)
  36.    {
  37.        for(int i=0; i<n2; i++) R.push_back(0);
  38.        std::copy(A.begin() + (l+n1), A.begin() + (l+n1+n2), R.begin());
  39.    }
  40.    std::vector<int>::iterator i = L.begin();
  41.    std::vector<int>::iterator j = R.begin();
  42.    std::vector<int>::iterator k = A.begin() + l;
  43.  
  44.    while(i != L.end() && j != R.end()) {
  45.        if(*i <= *j) {
  46.            *k = *i;
  47.            i++;
  48.        }
  49.        else {
  50.            *k = *j;
  51.            j++;
  52.        }
  53.        k++;
  54.    }
  55.  
  56.    while(i != L.end()) {
  57.        *k = *i;
  58.        i++;
  59.        k++;
  60.    }
  61.  
  62.    while(j != R.end()) {
  63.        *k = *j;
  64.        j++;
  65.        k++;
  66.    }
  67. }
  68.  
  69. void print_vector(std::vector<int> A) {
  70.  
  71.     std::vector<int>::iterator it;
  72.  
  73.     for(it = A.begin(); it != A.end(); ++it) {
  74.         std::cout << *it << " ";
  75.     }
  76. }
  77.  
  78.  
  79. int main() {
  80.     std::vector<int> A = {178, 1156, 136, 5, 6, 7};
  81.     mergesort(A, 0, A.size() - 1);
  82.  
  83.     print_vector(A);
  84.  
  85.     return 0;
  86. }
  87.  
Success #stdin #stdout 0s 16064KB
comments ()
stdin 
Standard input is empty
stdout 
5 6 7 136 178 1156
https://ideone.com/rNCFiH
language:
C++ (gcc 8.3)
created:
7 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!