In | Merges two subarrays of arr . First subarray is arr [ l . . m ] Second subarray is arr [ m + 1. . r ] Inplace Implementation ; If the direct merge is already sorted ; Two pointers to maintain start of both arrays to merge ; If element 1 is in right place ; Shift all the elements between element 1 element 2 , right by 1. ; Update all the pointers ; * l is for left index and r is right index of the sub - array of arr to be sorted ; Same as ( l + r ) / 2 , but avoids overflow for large l and r ; Sort first and second halves ; Function to pran array ; Driver program to test above functions
def merge ( arr , start , mid , end ) : NEW_LINE INDENT start2 = mid + 1 NEW_LINE if ( arr [ mid ] <= arr [ start2 ] ) : NEW_LINE INDENT return NEW_LINE DEDENT while ( start <= mid and start2 <= end ) : NEW_LINE INDENT if ( arr [ start ] <= arr [ start2 ] ) : NEW_LINE INDENT start += 1 NEW_LINE DEDENT else : NEW_LINE INDENT value = arr [ start2 ] NEW_LINE index = start2 NEW_LINE while ( index != start ) : NEW_LINE INDENT arr [ index ] = arr [ index - 1 ] NEW_LINE index -= 1 NEW_LINE DEDENT arr [ start ] = value NEW_LINE start += 1 NEW_LINE mid += 1 NEW_LINE start2 += 1 NEW_LINE DEDENT DEDENT DEDENT def mergeSort ( arr , l , r ) : NEW_LINE INDENT if ( l < r ) : NEW_LINE INDENT m = l + ( r - l ) // 2 NEW_LINE mergeSort ( arr , l , m ) NEW_LINE mergeSort ( arr , m + 1 , r ) NEW_LINE merge ( arr , l , m , r ) NEW_LINE DEDENT DEDENT def printArray ( A , size ) : NEW_LINE INDENT for i in range ( size ) : NEW_LINE INDENT print ( A [ i ] , end = " ▁ " ) NEW_LINE DEDENT print ( ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 12 , 11 , 13 , 5 , 6 , 7 ] NEW_LINE arr_size = len ( arr ) NEW_LINE mergeSort ( arr , 0 , arr_size - 1 ) NEW_LINE printArray ( arr , arr_size ) NEW_LINE DEDENT