merge sort makes log n recursive calls and each time calls merge ( ) which takes nlog n steps Time Complexity : O ( n * log n + 2 ( ( n / 2 ) * log ( n / 2 ) ) + 4 ( ( n / 4 ) * log ( n / 4 ) ) + ... . . + 1 ) Time Complexity : O ( logn * ( n * log n ) ) i . e . O ( n * ( logn ) ^ 2 ) Space Complexity : O ( 1 )
def mergeSort ( nums , s , e ) : NEW_LINE INDENT if s == e : NEW_LINE INDENT return NEW_LINE DEDENT DEDENT