question 343 Algorithms & Complexity · easy

Merge two sorted delivery lists and count the work

Two warehouses each send their delivery times sorted. Merging them takes one comparison every time the fronts of both lists are compared; once one list runs out, the rest of the other is copied without comparing. Write merge_sorted(first, second) that returns the merged list and the number of comparisons, showing the merge is O(n + m).

Functionmerge_sorted(first, second)

first, secondlists of numbers, each sorted ascending

Returnsa tuple (merged, comparisons): one sorted list with every value from both, and how many front-to-front comparisons were made

Ruleson equal fronts, take from first; don't change either input list

Examples

callmerge_sorted([5, 9, 14], [7, 9, 20])returns([5, 7, 9, 9, 14, 20], 5)

callmerge_sorted([1, 2], [3, 4, 5])returns([1, 2, 3, 4, 5], 2)

callmerge_sorted([], [8, 12])returns([8, 12], 0)