15mergesort.cpp

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

void merge(vector<int>&arr,int low,int mid,int high){
    //[low..mid]-->first subarray
    //[mid+1..high]-->2nd subarray
      int left=low;
      int right=mid+1;
      vector<int>temp;
      while(left<=mid&&right<=high){
          if(arr[left]<=arr[right]){
               temp.push_back(arr[left]);
               left++;
          }
          else{
            temp.push_back(arr[right]);
            right++;
          }
      }
      while(left<=mid){
        temp.push_back(arr[left]);
        left++;
      }
         while(right<=high){
        temp.push_back(arr[right]);
        right++;
      }

      for(int i=low;i<=high;i++){
        arr[i]=temp[i-low];
      }
}
void mergesort(vector<int>&arr,int low,int high){
     if(low==high)
     //agar ek element bacha hai thn return
     return;
     int mid=(low+high)/2;
     mergesort(arr,low,mid);
     mergesort(arr,mid+1,high);
     merge(arr,low,mid,high);

}

int main()
{
    int n;
    cout << "enter the size of the array" << endl;
    cin >> n;
    vector<int>arr(n);
    for(int i =0;i<n;i++){
        cin>>arr[i];
    }

    mergesort(arr, 0, n - 1);
    
    // Print the sorted array
    cout << "Sorted array: ";
    for (int i = 0; i < n; i++)
    {
        cout << arr[i] << " ";
    }
    
    cout << endl;

  

    return 0;
}