Merge K Sorted Lists - Divide & Conquer

Merge k sorted linked lists using divide and conquer with O(n log k) time complexity

K Linked Lists

Phase

Current operation

Active Pair

Lists being merged

Depth

Recursion level

K

Number of lists

Click "Step" or "Play" to start merging the k sorted lists

Inactive

Active

Comparing

Merged

Python Code - Merge K Sorted Lists

                def mergeKLists(lists):
            
                    if not lists:
            
                        return None
            
                    if len(lists) == 1:
            
                        return lists[0]
            
                    mid = len(lists) // 2
            
                    left = mergeKLists(lists[:mid])
            
                    right = mergeKLists(lists[mid:])
            
                    return _merge(left, right)
            
                def _merge(first, second):
            
                    dummy = ListNode()
            
                    tail = dummy
            
                    while first and second:
            
                        if first.val < second.val:
            
                            tail.next = first; first = first.next
            
                        else:
            
                            tail.next = second; second = second.next
            
                        tail = tail.next
            
                    tail.next = first or second
            
                    return dummy.next

Complexity Analysis

Time Complexity O(n log k) Space Complexity O(log k)

Time Complexity: O(n log k)

Breakdown

Merge levels: ⌈log k⌉ (k lists → 1 list)
Work per level: O(n) total nodes merged
Each node touched once per level
Total: O(log k) levels × O(n) = O(n log k)

T(n,k) = O(log k) levels × O(n) merge work = O(n log k)

Mathematical Intuition

Divide-and-conquer pairs up lists and merges: k lists → k/2 lists → k/4 lists → ... → 1 list. With ⌈log k⌉ merge rounds, and n total nodes processed per round, we get O(n log k). The naive approach (merge one at a time) costs O(n × k) because early lists are re-scanned.

Key Insight

Alternative: min-heap of k list heads yields O(n log k) by extracting minimum in O(log k) for each of n nodes. Same complexity, different constant factors.

Space Complexity: O(log k)

Breakdown

Recursion stack depth: O(log k)
Each frame: O(1) pointers
Merging: O(1) by pointer manipulation
No auxiliary arrays needed

S(k) = O(log k) — recursion stack only

Mathematical Intuition

The divide-and-conquer splits the list array in half recursively, giving O(log k) depth. Each merge operation uses constant extra space (dummy head, tail pointer). The heap approach uses O(k) space for the heap, which may be better or worse depending on k vs. log k.

Key Insight

Iterative pairwise merging (bottom-up) eliminates recursion entirely, achieving O(1) auxiliary space with O(k) pointers to track current lists.