Sort a Rotated Sorted Array | 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 code
def findStartIndexOfArray ( arr , low , high ) : NEW_LINE INDENT if ( low > high ) : NEW_LINE INDENT return - 1 ; NEW_LINE DEDENT if ( low == high ) : NEW_LINE INDENT return low ; NEW_LINE DEDENT mid = low + ( high - low ) / 2 ; NEW_LINE if ( arr [ mid ] > arr [ mid + 1 ] ) : NEW_LINE INDENT return mid + 1 ; NEW_LINE DEDENT if ( arr [ mid - 1 ] > arr [ mid ] ) : NEW_LINE INDENT return mid ; NEW_LINE DEDENT if ( arr [ low ] > arr [ mid ] ) : NEW_LINE INDENT return findStartIndexOfArray ( arr , low , mid - 1 ) ; NEW_LINE DEDENT else : NEW_LINE INDENT return findStartIndexOfArray ( arr , mid + 1 , high ) ; NEW_LINE DEDENT DEDENT def restoreSortedArray ( arr , n ) : NEW_LINE INDENT if ( arr [ 0 ] < arr [ n - 1 ] ) : NEW_LINE INDENT return ; NEW_LINE DEDENT start = findStartIndexOfArray ( arr , 0 , n - 1 ) ; NEW_LINE reverse ( arr , 0 , start ) ; NEW_LINE reverse ( arr , start , n ) ; NEW_LINE reverse ( arr ) ; NEW_LINE DEDENT def printArray ( arr , size ) : NEW_LINE INDENT for i in range ( size ) : NEW_LINE INDENT print ( arr [ i ] , end = " " ) ; NEW_LINE DEDENT DEDENT def reverse ( arr , i , j ) : NEW_LINE INDENT while ( i < j ) : NEW_LINE INDENT temp = arr [ i ] ; NEW_LINE arr [ i ] = arr [ j ] ; NEW_LINE arr [ j ] = temp ; NEW_LINE i += 1 ; NEW_LINE j -= 1 ; NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 1 , 2 , 3 , 4 , 5 ] ; NEW_LINE n = len ( arr ) ; NEW_LINE restoreSortedArray ( arr , n ) ; NEW_LINE printArray ( arr , n ) ; NEW_LINE DEDENT