Python3 program to sort an array using merge sort such that merge operation takes O ( 1 ) extra space .
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 DEDENT