fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. class Solution{
  5. public:
  6.     // Function to merge two sorted halves of the array
  7.     void merge(vector<int> &arr, int low, int mid, int high) {
  8.         // Temporary array to store merged elements
  9.         vector<int> temp;
  10.         int left = low;
  11.         int right = mid + 1;
  12.  
  13.         // Loop until subarrays are exhausted
  14.         while (left <= mid && right <= high) {
  15.             // Compare left and right elements
  16.             if (arr[left] <= arr[right]) {
  17.                 // Add left element to temp
  18.                 temp.push_back(arr[left]);
  19.                 // Move left pointer
  20.                 left++;
  21.             }
  22.             else {
  23.                 // Add right element to temp
  24.                 temp.push_back(arr[right]);
  25.                 // Move right pointer
  26.                 right++;
  27.             }
  28.         }
  29.  
  30.         // Adding the remaining elements of left half
  31.         while (left <= mid) {
  32.             temp.push_back(arr[left]);
  33.             left++;
  34.         }
  35.  
  36.         // Adding the remaining elements of right half
  37.         while (right <= high) {
  38.             temp.push_back(arr[right]);
  39.             right++;
  40.         }
  41.  
  42.         // Transferring the sorted elements to arr
  43.         for (int i = low; i <= high; i++) {
  44.             arr[i] = temp[i - low];
  45.         }
  46.     }
  47.  
  48.     // Helper function to perform merge sort from low to high
  49.     void mergeSortHelper(vector<int> &arr, int low, int high){
  50.         // Base case: if the array has only one element
  51.         if (low >= high)
  52.             return;
  53.  
  54.         // Find the middle index
  55.         int mid = (low + high) / 2;
  56.         // Recursively sort the left half
  57.         mergeSortHelper(arr, low, mid);
  58.         // Recursively sort the right half
  59.         mergeSortHelper(arr, mid + 1, high);
  60.         // Merge the sorted halves
  61.         merge(arr, low, mid, high);
  62.     }
  63.  
  64.     // Function to perform merge sort on the given array
  65.     vector<int> mergeSort(vector<int> &nums) {
  66.         int n = nums.size(); // SIze of array
  67.  
  68.         // Perform Merge sort on the whole array
  69.         mergeSortHelper(nums, 0, n-1);
  70.  
  71.         // Return the sorted array
  72.         return nums;
  73.     }
  74. };
  75.  
  76. int main(){
  77.     vector<int> arr = {9, 4, 7, 6, 3, 1, 5};
  78.     int n = arr.size();
  79.  
  80.     cout << "Before Sorting Array: " << endl;
  81.     for (int i = 0; i < n; i++)
  82.         cout << arr[i] << " ";
  83.     cout << endl;
  84.  
  85.     // Create an instance of the Solution class
  86.     Solution sol;
  87.     // Function call to sort the array
  88.     vector<int> sortedArr = sol.mergeSort(arr);
  89.  
  90.     cout << "After Sorting Array: " << endl;
  91.     for (int i = 0; i < n; i++)
  92.         cout << sortedArr[i] << " ";
  93.     cout << endl;
  94.  
  95.     return 0;
  96. }
Success #stdin #stdout 0s 5320KB
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/odYUF7
language:
C++ (gcc 8.3)
created:
2 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!