Merge Sort with O ( 1 ) extra space merge and O ( n lg n ) time [ Unsigned Integers Only ] | Python3 program to sort an array using merge sort such that merge operation takes O ( 1 ) extra space . ; Obtaining actual values ; Recursive merge sort with extra parameter , naxele ; This functions finds max element and calls recursive merge sort . ; Driver Code
def merge ( arr , beg , mid , end , maxele ) : NEW_LINE INDENT i = beg NEW_LINE j = mid + 1 NEW_LINE k = beg NEW_LINE while ( i <= mid and j <= end ) : NEW_LINE INDENT if ( arr [ i ] % maxele <= arr [ j ] % maxele ) : NEW_LINE INDENT arr [ k ] = arr [ k ] + ( arr [ i ] % maxele ) * maxele NEW_LINE k += 1 NEW_LINE i += 1 NEW_LINE DEDENT else : NEW_LINE INDENT arr [ k ] = arr [ k ] + ( arr [ j ] % maxele ) * maxele NEW_LINE k += 1 NEW_LINE j += 1 NEW_LINE DEDENT DEDENT while ( i <= mid ) : NEW_LINE INDENT arr [ k ] = arr [ k ] + ( arr [ i ] % maxele ) * maxele NEW_LINE k += 1 NEW_LINE i += 1 NEW_LINE DEDENT while ( j <= end ) : NEW_LINE INDENT arr [ k ] = arr [ k ] + ( arr [ j ] % maxele ) * maxele NEW_LINE k += 1 NEW_LINE j += 1 NEW_LINE DEDENT for i in range ( beg , end + 1 ) : NEW_LINE INDENT arr [ i ] = arr [ i ] // maxele NEW_LINE DEDENT DEDENT def mergeSortRec ( arr , beg , end , maxele ) : NEW_LINE INDENT if ( beg < end ) : NEW_LINE INDENT mid = ( beg + end ) // 2 NEW_LINE mergeSortRec ( arr , beg , mid , maxele ) NEW_LINE mergeSortRec ( arr , mid + 1 , end , maxele ) NEW_LINE merge ( arr , beg , mid , end , maxele ) NEW_LINE DEDENT DEDENT def mergeSort ( arr , n ) : NEW_LINE INDENT maxele = max ( arr ) + 1 NEW_LINE mergeSortRec ( arr , 0 , n - 1 , maxele ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 999 , 612 , 589 , 856 , 56 , 945 , 243 ] NEW_LINE n = len ( arr ) NEW_LINE mergeSort ( arr , n ) NEW_LINE print ( " Sorted ▁ array " ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT print ( arr [ i ] , end = " ▁ " ) NEW_LINE DEDENT DEDENT