# 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) ```python 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]].