Merge Sort

O(n log n)

Active Merge Range

Current Element (k)

Fully Sorted

Speed

mergeSort(arr, l, r): if l < r: m = (l + r) / 2 mergeSort(arr, l, m) mergeSort(arr, m + 1, r) merge(arr, l, m, r)

Best/Avg/Worst	O(n log n)
Space	O(n)