Quick sort 3 partition

quicksort3.cpp

#include<bits/stdc++.h>
using namespace std;
pair<int , int> partition3(int arr[] , int l , int r){
    pair<int , int> p;
    int pivot = arr[l];
    int high = l;
    for(int i = l+1 ; i<=r; i++){
        if(arr[i]<=pivot){
            high++;
            swap(arr[i],arr[high]);
        }
    }
    swap(arr[l] , arr[high]);
    int low = high;
    for(int i = high-1 ; i>=l ; i--){
        if(arr[i]==pivot){
            --low;
            swap(arr[low],arr[i]);
        }
    }

    p.first = low;
    p.second = high;
    return p;
}
void quick3(int arr[] , int l , int r){
    if(l>=r){
        return;
    }
    random_device rd; 
    mt19937 gen(rd()); 
    uniform_int_distribution<> distr(l, r); 
    int pivot = distr(gen);
    swap(arr[l] , arr[pivot]);
    pair<int , int> m = partition3(arr,l,r);
    quick3(arr , l , m.first-1);
    quick3(arr , m.second+1 , r);
}
int main(){
    int n;
    cin>>n;
    int arr[n];
    for(int i = 0 ; i<n ; i++){
        cin>>arr[i];
    }
    quick3(arr , 0 , n-1);
    for(int i = 0 ; i<n ; i++){
        cout<<arr[i]<<" ";
    }
}