fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. void merge(vector<int>& arr, int left, 
  4.                      int mid, int right)
  5. {
  6.     int n1 = mid - left + 1;
  7.     int n2 = right - mid;
  8.  
  9.     vector<int> L(n1), R(n2);
  10.  
  11.     for (int i = 0; i < n1; i++)
  12.         L[i] = arr[left + i];
  13.     for (int j = 0; j < n2; j++)
  14.         R[j] = arr[mid + 1 + j];
  15.  
  16.     int i = 0, j = 0;
  17.     int k = left;
  18.  
  19.     while (i < n1 && j < n2) {
  20.         if (L[i] <= R[j]) {
  21.             arr[k] = L[i];
  22.             i++;
  23.         }
  24.         else {
  25.             arr[k] = R[j];
  26.             j++;
  27.         }
  28.         k++;
  29.     }
  30.  
  31.     while (i < n1) {
  32.         arr[k] = L[i];
  33.         i++;
  34.         k++;
  35.     }
  36.  
  37.     while (j < n2) {
  38.         arr[k] = R[j];
  39.         j++;
  40.         k++;
  41.     }
  42. }
  43.  
  44. void mergeSort(vector<int>& arr, int left, int right)
  45. {
  46.     if (left >= right)
  47.         return;
  48.  
  49.     int mid = left + (right - left) / 2;
  50.     mergeSort(arr, left, mid);
  51.     mergeSort(arr, mid + 1, right);
  52.     merge(arr, left, mid, right);
  53. }
  54.  
  55.  
  56. void printVector(vector<int>& arr)
  57. {
  58.     for (int i = 0; i < arr.size(); i++)
  59.         cout << arr[i] << " ";
  60.     cout << endl;
  61. }
  62.  
  63. // Driver code
  64. int main()
  65. {
  66.     vector<int> arr = {8,3,7,4,2,6,5,1};
  67.     int n = arr.size();
  68.  
  69.     cout << "Given vector is: \n";
  70.     printVector(arr);
  71.  
  72.     mergeSort(arr, 0, n - 1);
  73.  
  74.     cout << "Sorted vector is: \n";
  75.     printVector(arr);
  76.     return 0;
  77. }
Success #stdin #stdout 0s 5276KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Given vector is: 
8 3 7 4 2 6 5 1 
Sorted vector is: 
1 2 3 4 5 6 7 8
https://ideone.com/Lq1tJz
Merge sort by Radiathun Tasnia
language:
C++14 (gcc 8.3)
created:
8 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!