Merge Sort as D&C

Merge sort is the textbook D&C example.

Divide: Split the array into two halves. Conquer: Recursively sort each half. Combine: Merge the two sorted halves.

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)

Why D&C works here: Merging two sorted arrays is $O(n)$. Sorting each half is a smaller version of the same problem. The recurrence $T(n) = 2T(n/2) + O(n)$ gives $T(n) = O(n \log n)$.