Merge K Sorted Arrays (Combine K Sorted Arrays into One Sorted Array)

• Merge K Sorted Arrays is the array form of the K-way Merge pattern.
• Each heap entry stores {value, arrayIndex, elementIndex} to track the source.
• We seed the heap with the first element of each non-empty array.
• We repeatedly pop the global minimum into the output and push the next element from the same array.
• The heap holds at most K candidates at any time.
• Time is O(N log K) and space is O(K) for the heap plus O(N) for the output.

What is the Merge K Sorted Arrays problem?

Given K sorted arrays, merge them into a single sorted array containing all elements. This is the array analog of merging K sorted linked lists. The challenge is to do it efficiently without simply concatenating and re-sorting.

How does the min-heap approach work?

We use a min-heap that always holds one candidate from each non-empty array. Each heap entry stores three values: the element value, the index of the source array, and the index of the element within that array. We repeatedly pop the smallest element and push its successor.

package com.bank.service;

import java.util.PriorityQueue;

public class MergeKArraysService {

    /**
     * Merges K sorted settlement arrays into one sorted array.
     * Used by the National Bank of India reconciliation team.
     */
    public static int[] mergeKArrays(int[][] desks) {
        // Count total elements and pre-size output
        int totalElements = 0;
        for (int[] desk : desks) totalElements += desk.length;
        int[] result = new int[totalElements];

        // Heap entry: {value, arrayIndex, elementIndex}
        PriorityQueue<int[]> minHeap = new PriorityQueue<>(
            (a, b) -> Integer.compare(a[0], b[0]));

        // Seed with first element of each non-empty array
        for (int i = 0; i < desks.length; i++) {
            if (desks[i].length > 0) {
                minHeap.offer(new int[]{desks[i][0], i, 0});
            }
        }

        int idx = 0;
        while (!minHeap.isEmpty()) {
            int[] entry = minHeap.poll();
            int val = entry[0], ai = entry[1], ei = entry[2];
            result[idx++] = val;

            // Push successor from the same array
            if (ei + 1 < desks[ai].length) {
                minHeap.offer(new int[]{desks[ai][ei + 1], ai, ei + 1});
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[][] desks = {
            {1000, 3000, 5000},
            {2000, 4000, 6000},
            {1500, 3500}
        };
        int[] merged = mergeKArrays(desks);
        System.out.print("Merged settlements: ");
        for (int val : merged) System.out.print(val + " ");
        System.out.println();
    }
}

javac -d out com/bank/service/MergeKArraysService.java
java -cp out com.bank.service.MergeKArraysService

Merged settlements: 1000 1500 2000 3000 3500 4000 5000 6000

Why is the heap entry a triple?

With arrays, we cannot follow a next pointer as with linked lists. The array index tells us which source array the element came from, and the element index tells us where to find the next element within that array. Without these two indices, we would not know where to fetch the successor after popping.

Why is this better than concatenating and sorting?

Concatenating all K arrays and sorting the result costs O(N log N). The heap-based K-way merge costs O(N log K). Since K <= N (and usually K is much smaller), log K <= log N, so the heap approach is strictly better. The improvement is significant when K is small relative to N.

| Approach | Time | Space |
|---|---|---|
| Concatenate and sort | O(N log N) | O(N) |
| K-way merge with heap | O(N log K) | O(N + K) |
| Pairwise merge | O(N log K) | O(N) |

What are the edge cases?

Several edge cases require attention.

• Empty arrays: skip them during seeding. If all arrays are empty, return an empty array.
• Single array: the heap has one element, and the result is just a copy of that array.
• Arrays of different lengths: handled naturally because each array tracks its own element index.
• Duplicate values: the heap handles duplicates correctly; they are popped in order.

package com.bank.core;

public class MergeEdgeCases {
    public static void main(String[] args) {
        // One empty array
        int[][] desks = {{1000, 2000}, {}, {1500}};
        int[] merged = MergeKArraysService.mergeKArrays(desks);
        for (int v : merged) System.out.print(v + " ");
        System.out.println(); // 1000 1500 2000

        // All empty
        int[][] empty = {{}, {}, {}};
        int[] result = MergeKArraysService.mergeKArrays(empty);
        System.out.println("Length: " + result.length); // 0
    }
}

1000 1500 2000
Length: 0

What is the time and space complexity?

Each of the N total elements is pushed and popped from the heap exactly once. Each push and pop costs O(log K) because the heap holds at most K elements. Total time is O(N log K). Space is O(K) for the heap plus O(N) for the output.

How does pairwise merging compare?

An alternative is to merge arrays pairwise: merge the first two arrays, then merge the result with the third, and so on. This is O(N * K) in the worst case if done naively. Using a divide-and-conquer pairwise strategy (merge pairs in rounds) achieves O(N log K) like the heap approach, with simpler code but potentially higher constant factors.

What should a senior engineer know?

A senior engineer should understand these deeper aspects.

• Pre-sizing: allocate the output array to the known total size to avoid dynamic resizing, which matters when N is large.
• Stability: the heap-based merge is stable if ties are broken by array index and element index, preserving the original order of equal elements.
• Streaming: in a streaming scenario where arrays arrive incrementally, the heap approach naturally accommodates new arrays by adding their first element to the heap.
• External merge sort: this K-way merge is the core operation in external sorting, where K sorted runs on disk are merged into a single sorted file.