How do two index pointers merge sorted lists in linear time, and why do log n levels of merging add up to n log n?
Short drills on what this video just taught. Write the code, run the checks, and reveal the answer only if you are stuck.
Run the video's merge by hand on left = [3, 9, 10] and right = [1, 2, 7, 12, 15], moving i and j as the first while loop does. Count how many times left[i] < right[j] is evaluated before that loop ends, and note which elements the trailing loops then copy. Assign the count to comparisons and the copied elements, in order, as a list to leftover.