fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. void merge(vector<int> &arr, int low, int mid, int high) {
  5.     vector<int> temp; // temporary array
  6.     int left = low;      // starting index of left half of arr
  7.     int right = mid + 1;   // starting index of right half of arr
  8.  
  9.     //storing elements in the temporary array in a sorted manner//
  10.  
  11.     while (left <= mid && right <= high) {
  12.         if (arr[left] <= arr[right]) {
  13.             temp.push_back(arr[left]);
  14.             left++;
  15.         }
  16.         else {
  17.             temp.push_back(arr[right]);
  18.             right++;
  19.         }
  20.     }
  21.  
  22.     // if elements on the left half are still left //
  23.  
  24.     while (left <= mid) {
  25.         temp.push_back(arr[left]);
  26.         left++;
  27.     }
  28.  
  29.     //  if elements on the right half are still left //
  30.     while (right <= high) {
  31.         temp.push_back(arr[right]);
  32.         right++;
  33.     }
  34.  
  35.     // transfering all elements from temporary to arr //
  36.     for (int i = low; i <= high; i++) {
  37.         arr[i] = temp[i  - low];
  38.     }
  39. }
  40.  
  41. void mergeSort(vector<int> &arr, int low, int high) {
  42.     if (low >= high) return;
  43.     int mid = (low + high) / 2 ;
  44.     mergeSort(arr, low, mid);  // left half
  45.     mergeSort(arr, mid + 1, high); // right half
  46.     merge(arr, low, mid, high);  // merging sorted halves
  47. }
  48.  
  49. int main() {
  50.  
  51.     vector<int> arr = {9, 4, 7, 6, 3, 1, 5}  ;
  52.     int n = 7;
  53.  
  54.     cout << "Before Sorting Array: " << endl;
  55.     for (int i = 0; i < n; i++) {
  56.         cout << arr[i] << " "  ;
  57.     }
  58.     cout << endl;
  59.     mergeSort(arr, 0, n - 1);
  60.     cout << "After Sorting Array: " << endl;
  61.     for (int i = 0; i < n; i++) {
  62.         cout << arr[i] << " "  ;
  63.     }
  64.     cout << endl;
  65.     return 0 ;
  66. }
Success #stdin #stdout 0.01s 5264KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Before Sorting Array: 
9 4 7 6 3 1 5 
After Sorting Array: 
1 3 4 5 6 7 9
https://ideone.com/LY09WE
language:
C++ (gcc 8.3)
created:
3 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!