Merge Sort Algorithm Tutorial

Merge Sort

Merge Sort is a divide-and-conquer sorting algorithm that splits the array in half, recursively sorts each half, then merges the sorted halves. It guarantees $O(n \log n)$ time in all cases.

In the merge step, you combine two sorted arrays into one sorted array in linear time.

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):
    temp = empty array
    i = left
    j = mid + 1

    while i <= mid and j <= right:
        if arr[i] <= arr[j]:
            temp.append(arr[i])
            i = i + 1
        else:
            temp.append(arr[j])
            j = j + 1

    while i <= mid:
        temp.append(arr[i])
        i = i + 1
    while j <= right:
        temp.append(arr[j])
        j = j + 1

    copy temp back to arr[left..right]

Stability: Merge Sort is stable. Equal elements maintain their relative order. You'll use this when sorting objects by multiple keys.

Why $O(n \log n)$: You divide the array $\log n$ times, and each level requires $O(n)$ work for merging.

Applications: You use Merge Sort for external sorting (large files), linked list sorting, counting inversions, and stable sorting requirements.

Time complexity: $O(n \log n)$ in all cases.

Space complexity: $O(n)$ for the temporary array during merging.