🧩 Python DSA Patterns — K-Way Merge 🔀🐍

Merging two sorted arrays is simple. But what if you must merge K sorted lists? A brute-force approach compares every list repeatedly, leading to inefficient solutions.

The K-Way Merge pattern optimises this using:

• 🔼 Min Heap (Priority Queue)
• 🔀 Divide & Conquer merging

This reduces complexity significantly and appears frequently in advanced array and linked list problems.

🧠 Core Idea

At any time, the smallest element among all lists must be chosen next.

Instead of scanning all lists:

• Push one element from each list into a min heap
• Extract the smallest
• Insert the next element from the same list

This ensures we always pick the correct next value efficiently.

📝 Merge K Sorted Arrays (Min Heap Approach)

import heapq

def merge_k_arrays(arrays):
    heap = []
    result = []

    for i, arr in enumerate(arrays):
        if arr:
            heapq.heappush(heap, (arr[0], i, 0))

    while heap:
        val, arr_i, elem_i = heapq.heappop(heap)
        result.append(val)

        if elem_i + 1 < len(arrays[arr_i]):
            heapq.heappush(
                heap,
                (arrays[arr_i][elem_i + 1], arr_i, elem_i + 1)
            )

    print("Merged Arrays:", result)

💡 Why this works:

The heap always keeps the smallest available element at the top.

📝 Merge K Sorted Linked Lists

This extends the same logic to linked lists.

def merge_k_lists(lists):
    heap = []
    dummy = ListNode()
    tail = dummy

    for i, node in enumerate(lists):
        if node:
            heapq.heappush(heap, (node.val, i, node))

    while heap:
        val, i, node = heapq.heappop(heap)
        tail.next = node
        tail = tail.next

        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))

    return dummy.next

📝 Divide & Conquer Merge

Instead of a heap, merge lists pairwise like merge sort.

def merge_k_lists_divide(lists):
    if not lists:
        return None

    while len(lists) > 1:
        merged = []
        for i in range(0, len(lists), 2):
            l1 = lists[i]
            l2 = lists[i+1] if i+1 < len(lists) else None
            merged.append(merge_two_lists(l1, l2))
        lists = merged

    return lists[0]

💡 Observation:

Both heap and divide & conquer approaches run in:

O(N log K)

Where:

• N = total elements
• K = number of lists

🧠 Where This Pattern Is Used

• 🔗 Merge K sorted linked lists
• 📊 Merge multiple sorted arrays
• 🗂️ External sorting systems
• 🌊 Streaming sorted data
• 🧩 Advanced interval merging

✅ Takeaway

• Heap keeps the smallest candidate ready
• Divide & conquer mirrors merge sort
• Reduces complexity from O(NK) to O(N log K)
• A powerful extension of heap and merge techniques

This is one of the most important multi-structure merging patterns in DSA.

🏋️ Practice Problems

1. Merge K Sorted Lists
2. Kth Smallest Element in Sorted Matrix
3. Smallest Range Covering Elements from K Lists
4. Merge K Sorted Arrays
5. External Sorting Simulation

📂 Full Script

The blog covers the essentials — find the complete notebook with all snippets & extras on GitHub Repo 👉 Python DSA Patterns