Merge Sort

• divide-and-conquer technique
• Divide into subarrays by calculating the midpoint
• Combine the two adjacent sorted arrays (as if merging two decks of cards)

def merge_sort(A, p, r)
    if p >= r
        return
    q = floor((p + r) / 2)
    merge_sort(A, p, q)
    merge_sort(A, q + 1, r)
    merge(A, p, q, r)

$$T(n)=2T(n/2)+\Theta (n)=\Theta (n\lg n)$$

• The merge process is equivalent to scanning through the real axis and “report” the first number encountered.

$k$-Merge Sort

$$T(n)=kT(n/k)+an\lg k$$

• Get the minimum using min-heap
• When $k=n$, merge sort becomes heapsort.