text: Sort a Rotated Sorted Array | C ++ implementation for restoring original sort in rotated sorted array using binary search ; Function to find start index of array ; Function to restore the Original Sort ; array is already sorted ; In reverse ( ) , the first parameter is iterator to beginning element and second parameter is iterator to last element plus one . ; Function to print the Array ; Driver function
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; int findStartIndexOfArray ( int arr [ ] , int low , int high ) { if ( low > high ) { return -1 ; } if ( low == high ) { return low ; } int mid = low + ( high - low ) / 2 ; if ( arr [ mid ] > arr [ mid + 1 ] ) return mid + 1 ; if ( arr [ mid - 1 ] > arr [ mid ] ) return mid ; if ( arr [ low ] > arr [ mid ] ) return findStartIndexOfArray ( arr , low , mid - 1 ) ; else return findStartIndexOfArray ( arr , mid + 1 , high ) ; } void restoreSortedArray ( int arr [ ] , int n ) { if ( arr [ 0 ] < arr [ n - 1 ] ) return ; int start = findStartIndexOfArray ( arr , 0 , n - 1 ) ; reverse ( arr , arr + start ) ; reverse ( arr + start , arr + n ) ; reverse ( arr , arr + n ) ; } void printArray ( int arr [ ] , int size ) { for ( int i = 0 ; i < size ; i ++ ) cout << arr [ i ] << " ▁ " ; } int main ( ) { int arr [ ] = { 1 , 2 , 3 , 4 , 5 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; restoreSortedArray ( arr , n ) ; printArray ( arr , n ) ; return 0 ; }