Merging many by merging two, repeatedly

Pair them up and merge in rounds. The complexity difference against the obvious approach is the lesson.

The obvious approach, and its cost

You can already merge two sorted lists. To merge k of them, the obvious move is to merge the first two, then merge that result with the third, and so on.

That is correct and slow. The accumulator grows by n nodes each round and is walked in full every time, so the total work is n, then 2n, then 3n, and so on up to k rounds. That sums to about n times k squared over two, which is O(n k squared).

Why it works

Merge in rounds instead

Pair the lists up and merge each pair. That halves how many lists remain. Repeat until one is left.

Every round touches every node exactly once, so a round costs O(n k). The number of rounds is how many times you can halve k, which is log k. Total O(n k log k), and the difference against the accumulating version grows fast with k.

Only the count matters for that argument, so watch it rather than the contents. Five lists take three rounds, not five.

1count = 52round_number = 03 4while count > 1:5    round_number += 16    pairs = count // 27    carried = count % 2                  # an odd one out rides to the next round8    print(f"round {round_number}: {count} lists become {pairs + carried}")9    count = pairs + carried

Each round halves the count, so the number of rounds is log k.

Complexity· 5 min

Cost of the accumulating approach

Suppose you merge k sorted lists by repeatedly merging the running result with the next list. With k lists of n nodes each, what is the total time? Give space as the extra space beyond the output.

Python

1result = lists[0]2for i in range(1, len(lists)):3    result = merge_two(result, lists[i])4return result

Problem· 32 min

Merge K Sorted Lists

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

CodeGround