fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. void merge(vector<int>& arr, int left, 
  5.                      int mid, int right)
  6. {
  7.     int n1 = mid - left + 1;
  8.     int n2 = right - mid;
  9.     vector<int> L(n1), R(n2);
  10.     for (int i = 0; i < n1; i++)
  11.         L[i] = arr[left + i];
  12.     for (int j = 0; j < n2; j++)
  13.         R[j] = arr[mid + 1 + j];
  14.     int i = 0, j = 0;
  15.     int k = left;
  16.     while (i < n1 && j < n2) {
  17.         if (L[i] <= R[j]) {
  18.             arr[k] = L[i];
  19.             i++;
  20.         }
  21.         else {
  22.             arr[k] = R[j];
  23.             j++;
  24.         }
  25.         k++;
  26.     }
  27.     while (i < n1) {
  28.         arr[k] = L[i];
  29.         i++;
  30.         k++;
  31.     }
  32.     while (j < n2) {
  33.         arr[k] = R[j];
  34.         j++;
  35.         k++;
  36.     }
  37. }
  38. void mergeSort(vector<int>& arr, int left, int right)
  39. {
  40.     if (left >= right)
  41.         return;
  42.  
  43.     int mid = left + (right - left) / 2;
  44.     mergeSort(arr, left, mid);
  45.     mergeSort(arr, mid + 1, right);
  46.     merge(arr, left, mid, right);
  47. }
  48.  
  49. void printVector(vector<int>& arr)
  50. {
  51.     for (int i = 0; i < arr.size(); i++)
  52.         cout << arr[i] << " ";
  53.     cout << endl;
  54. }
  55.  
  56.  
  57. int main()
  58. {
  59.     vector<int> arr = { 12, 11, 13, 5, 6, 7 };
  60.     int n = arr.size();
  61.  
  62.     cout << "Given vector is \n";
  63.     printVector(arr);
  64.     clock_t begin = clock(); 
  65.     mergeSort(arr, 0, n - 1);
  66.     cout << "\nSorted vector is \n";
  67.     printVector(arr);
  68.     clock_t end = clock();
  69.     cout<<"Time run: "<<fixed << (float)(end-begin)/CLOCKS_PER_SEC<<" s"<<endl;
  70.     return 0;
  71. }
  72.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Given vector is 
12 11 13 5 6 7 

Sorted vector is 
5 6 7 11 12 13 
Time run: 0.000010 s
https://ideone.com/9HSjdt
language:
C++14 (gcc 8.3)
created:
14 days 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!