Merge Sort - Code

Here is the implementation of merge sort:

function mergeSort(arr, left, right):
    if left >= right:
        return
    mid = (left + right) / 2
    mergeSort(arr, left, mid)
    mergeSort(arr, mid+1, right)
    merge(arr, left, mid, right)

function merge(arr, left, mid, right):
    create temp arrays L and R
    copy arr[left..mid] to L
    copy arr[mid+1..right] to R
    merge L and R back into arr[left..right]

Time: $O(n \log n)$ always. Each level of recursion does $O(n)$ work. There are $\log n$ levels.

Space: $O(n)$ for the temporary arrays during merge (excluding input array).

Stability: Stable. When equal elements compare, take from the left array first.