150. Merge K Sorted Arrays by Divide-and-Conquer

Why this mechanism works

Define a call over a half-open range of source lists. It returns the sorted merge of exactly those sources. Split that range in half, obtain two sorted child results, and merge them with kata 021. Balanced splitting prevents repeatedly merging a growing result with one small next list.

State and boundaries

merge_range(left,right) owns source indices [left,right). Its returned list contains every occurrence from those sources in sorted order.

Protocol

1. Return [] for an empty source range.
2. Copy the sole source for a singleton range.
3. Split the source range at its midpoint.
4. Recursively merge both halves.
5. Merge the two child outputs.

Visualization

sources A B C D
merge(A,B) | merge(C,D)
          merge both results
logarithmic merge levels

Python implementation

from kata_021 import merge_sorted

def merge_k_divide(arrays):
    def merge_range(left, right):
        if left == right:
            return []
        if right - left == 1:
            return list(arrays[left])
        mid = (left + right) // 2
        a = merge_range(left, mid)
        b = merge_range(mid, right)
        return merge_sorted(a, b)
    return merge_range(0, len(arrays))

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L4 merge_k_divide: def merge_range(left, right):
arrays=[[1, 4], [2, 3], [0, 5]]

L5 merge_range: if left == right:
left=0; right=3; arrays=[[1, 4], [2, 3], [0, 5]]

L9 merge_range: mid = (left + right) // 2
left=0; right=3; arrays=[[1, 4], [2, 3], [0, 5]]; mid=1

L5 merge_range: if left == right:
left=0; right=1; arrays=[[1, 4], [2, 3], [0, 5]]

L10 merge_range: a = merge_range(left, mid)
left=0; right=3; arrays=[[1, 4], [2, 3], [0, 5]]; mid=1; a=[1, 4]

L5 merge_range: if left == right:
left=1; right=3; arrays=[[1, 4], [2, 3], [0, 5]]

L9 merge_range: mid = (left + right) // 2
left=1; right=3; arrays=[[1, 4], [2, 3], [0, 5]]; mid=2

L5 merge_range: if left == right:
left=1; right=2; arrays=[[1, 4], [2, 3], [0, 5]]

L10 merge_range: a = merge_range(left, mid)
left=1; right=3; arrays=[[1, 4], [2, 3], [0, 5]]; mid=2; a=[2, 3]

L5 merge_range: if left == right:
left=2; right=3; arrays=[[1, 4], [2, 3], [0, 5]]

L11 merge_range: b = merge_range(mid, right)
left=1; right=3; arrays=[[1, 4], [2, 3], [0, 5]]; mid=2; a=[2, 3]; b=[0, 5]

L11 merge_range: b = merge_range(mid, right)
left=0; right=3; arrays=[[1, 4], [2, 3], [0, 5]]; mid=1; a=[1, 4]; b=[0, 2, 3, 5]

L4 merge_k_divide: def merge_range(left, right):
arrays=[[], [2, 2], []]

L5 merge_range: if left == right:
left=0; right=3; arrays=[[], [2, 2], []]

L9 merge_range: mid = (left + right) // 2
left=0; right=3; arrays=[[], [2, 2], []]; mid=1

L5 merge_range: if left == right:
left=0; right=1; arrays=[[], [2, 2], []]

L10 merge_range: a = merge_range(left, mid)
left=0; right=3; arrays=[[], [2, 2], []]; mid=1; a=[]

L5 merge_range: if left == right:
left=1; right=3; arrays=[[], [2, 2], []]

L9 merge_range: mid = (left + right) // 2
left=1; right=3; arrays=[[], [2, 2], []]; mid=2

L5 merge_range: if left == right:
left=1; right=2; arrays=[[], [2, 2], []]

L10 merge_range: a = merge_range(left, mid)
left=1; right=3; arrays=[[], [2, 2], []]; mid=2; a=[2, 2]

L5 merge_range: if left == right:
left=2; right=3; arrays=[[], [2, 2], []]

L11 merge_range: b = merge_range(mid, right)
left=1; right=3; arrays=[[], [2, 2], []]; mid=2; a=[2, 2]; b=[]

L11 merge_range: b = merge_range(mid, right)
left=0; right=3; arrays=[[], [2, 2], []]; mid=1; a=[]; b=[2, 2]

Why the solution is correct

The empty and singleton source ranges satisfy the contract directly. If both child outputs correctly merge their disjoint source subsets, merging them produces the correct sorted union for the parent range. Balanced source partitioning establishes the result for all k lists.

Time and space

O(N log(k+1)+k) time for N total values; O(N+k) conservative peak storage and O(log(k+1)) call depth.

Common mistakes

Sequentially merging a growing accumulator may repeatedly copy early values across many stages. Splitting by source indices avoids unnecessary slicing of the outer list.

Reasoning card

Transfer exercise

Compare heap-frontier merging with divide-and-conquer when sources are live streams that cannot be reread or fully materialized.