fork download 
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. vector<int> Merge(const vector<int> &v1, const vector<int> &v2)
  7. {
  8.     vector<int> res;
  9.     int s1 = v1.size(), s2 = v2.size(), i, j;
  10.     /*
  11.     cout << endl;
  12.     for (int i = 0; i < s1; ++i)
  13.         cout << v1[i] << " ";
  14.     cout << endl;
  15.     for (int i = 0; i < s2; ++i)
  16.         cout << v2[i] << " ";
  17.     cout << endl;
  18.     */
  19.     for (i = 0, j = 0; i < s1, j < s2;) {
  20.         if (v1[i] <= v2[j]) {
  21.             res.push_back(v1[i]);
  22.             ++i;
  23.         }
  24.         else {
  25.             res.push_back(v2[j]);
  26.             ++j;
  27.         }
  28.     }
  29.     if (i < s1) {
  30.         for (int var = i; var < s1; ++var)
  31.             res.push_back(v1[var]);
  32.     }
  33.     else {
  34.         for (int var = j; var < s2; ++var)
  35.             res.push_back(v2[var]);
  36.     }
  37.     return res;
  38. }
  39.  
  40. vector<int> mergeSort(const vector<int> &arr, int left, int right)
  41. {
  42.     // 3 9 7 1 5 4 2
  43.     if (left == right) return vector<int>{arr[left]};
  44.     int m = (left + right) / 2;
  45.     vector<int> first = mergeSort(arr, left, m);
  46.     vector<int> second = mergeSort(arr, m + 1, right);
  47.     vector<int> res = Merge(first, second);
  48.     /*
  49.     for (auto &it : res) cout << it << " ";
  50.     cout << endl;
  51.     */
  52.     return res;
  53. }
  54.  
  55. int main()
  56. {
  57.     vector<int> arr{3, 9, 7, 1, 5, 4, 2};
  58.     vector<int> res = mergeSort(arr, 0, arr.size() - 1);
  59.     for (auto &it : res) cout << it << " ";
  60.     return 0;
  61. }
  62.  
Success #stdin #stdout 0s 15240KB
comments (?)
stdin 
Standard input is empty
stdout 
1 2 3 0 0 0 0 0 4 5 7 9
https://ideone.com/0IxVy4
language:
C++14 (gcc 8.3)
created:
6 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!