Two-Pointer Merge Passes

Foundations

In the first lesson, merge sort did all of its comparing while merging sorted halves. Now, what if the input arrives as two runs that are already sorted, and you only need them combined?

A run is a stretch of elements already in order. Merging two runs keeps one pointer at the front of each: compare the two front values, append the smaller, and advance that pointer. When one run is used up, the rest of the other is appended as is. Each step places one value, so runs of lengths n and m merge in n + m steps, O(n + m), with no sorting at all.

Sort the first three values of nums = [7, 1, 5, 3, 6] and the last two on their own: the runs are a = [1, 5, 7] and b = [3, 6]. Compare fronts: 1 beats 3, 3 beats 5, 5 beats 6, and 6 beats 7. Now b is used up, so 7 is appended. Five values merged in 5 steps and 4 comparisons into [1, 3, 5, 6, 7].

Case Scenario

Merge Sorted Array hands you both runs in one array: the first m slots of nums1 and all of nums2, with n empty slots at the end of nums1 to fill. Merging from the front would overwrite unread values, so the pointers start at the backs and fill the empty tail largest first. For nums1 = [1, 2, 3, 0, 0, 0] and nums2 = [2, 5, 6], the result is [1, 2, 2, 3, 5, 6].

The direct approach copies nums2 into the empty slots and sorts all m + n values: O((m + n) log(m + n)) time. It throws away the fact that both runs were already sorted, and the sort can need O(m + n) extra memory, while a merge only ever compares two front values.