Concept:

Divide and conquer:

Let the merge sort recursive function be F. Call F for left half subarray and right half sorted array.

Now merge the two sorted array into one complete sorted array.

Merge takes O(n) and the depth of the recursive tree is Log(n).

Complete complexity: N * Log(n).

def merge_sort(arr): _merge_sort(arr, 0, len(arr) - 1) return arr def _merge_sort(arr, left_index, right_index): if left_index < right_index: mid_index = (left_index + right_index) / 2 _merge_sort(arr, left_index, mid_index) _merge_sort(arr, mid_index + 1, right_index) merge_two_sorted_arrays(arr, left_index, mid_index, mid_index + 1, right_index) return arr def merge_two_sorted_arrays(arr, left_start_index, left_end_index, right_start_index, right_end_index): result = [] i = left_start_index j = right_start_index while i < len(left_end_index) and j < len(right_end_index): if arr[i] < arr[j]: result.append(arr[i]) i += 1 else: result.append(arr[j]) j += 1 result.extend(arr[i:left_end_index + 1]) result.extend(arr[j:right_end_index + 1]) arr = result