Advertisement
Home Data Structure Arrays Merge K Sorted Arrays

Merge K Sorted Arrays

0
Advertisement

Title: Merge K Sorted Arrays

In this guide, you’ll learn how to merge k sorted arrays into a single sorted array using Java. This is a classic interview question that checks whether you can combine a heap with the fact that every input array is already sorted, instead of just concatenating everything and sorting from scratch.

We’ll walk through the approach, a complete working program, a step-by-step trace, two worked examples, common mistakes, edge cases to test, and a set of interview follow-up questions so you can reason about the problem under pressure, not just memorize the code.

Understanding the Problem

You are given k arrays, each already sorted in ascending order, but the arrays can have different lengths. The task is to combine all of them into one array that contains every element from every input array, still sorted in ascending order.

A brute-force solution copies every element into one big array and sorts it, which costs O(n log n) time where n is the total number of elements across all arrays. That approach throws away useful information: each array is already sorted. A min-heap lets you repeatedly pick the smallest remaining element across all k arrays in O(log k) time per pick, bringing the total cost down to O(n log k).

Approach to Merge K Sorted Arrays

The idea is to never look at more than one unconsumed element per array at a time. A min-heap keeps track of the smallest of those k candidates so you always know which element to emit next.

  1. Create a PriorityQueue (min-heap) of nodes, where each node stores a value, the index of the array it came from, and the position of that value inside its array.
  2. Seed the heap by inserting the first element of every non-empty array, along with its array index and element index 0.
  3. While the heap is not empty, remove the node holding the smallest value and append that value to the result array.
  4. Check whether the array the removed node came from has a next element. If it does, insert that next element into the heap with its array index and incremented element index.
  5. Repeat steps 3 and 4 until the heap is empty, at which point every element from every array has been moved into the result.
  6. Return the result array, which now holds all elements from all k arrays in sorted order.

Java Program to Merge K Sorted Arrays

The program below defines a small HeapNode helper class so the heap can track which array and position each value came from, then drives the merge with a PriorityQueue.

Java
import java.util.PriorityQueue;

public class MergeKSortedArrays {

    static class HeapNode implements Comparable<HeapNode> {
        int value;
        int arrayIndex;
        int elementIndex;

        HeapNode(int value, int arrayIndex, int elementIndex) {
            this.value = value;
            this.arrayIndex = arrayIndex;
            this.elementIndex = elementIndex;
        }

        @Override
        public int compareTo(HeapNode other) {
            return Integer.compare(this.value, other.value);
        }
    }

    public static int[] mergeKArrays(int[][] arrays) {
        int k = arrays.length;
        int totalLength = 0;
        for (int[] arr : arrays) {
            totalLength += arr.length;
        }

        int[] result = new int[totalLength];
        PriorityQueue<HeapNode> minHeap = new PriorityQueue<>();

        for (int i = 0; i < k; i++) {
            if (arrays[i].length > 0) {
                minHeap.offer(new HeapNode(arrays[i][0], i, 0));
            }
        }

        int index = 0;
        while (!minHeap.isEmpty()) {
            HeapNode node = minHeap.poll();
            result[index] = node.value;
            index++;

            int nextElementIndex = node.elementIndex + 1;
            if (nextElementIndex < arrays[node.arrayIndex].length) {
                int nextValue = arrays[node.arrayIndex][nextElementIndex];
                minHeap.offer(new HeapNode(nextValue, node.arrayIndex, nextElementIndex));
            }
        }

        return result;
    }

    public static void main(String[] args) {
        int[][] arrays = {
            {1, 4, 9},
            {2, 5, 10},
            {3, 6, 11, 15}
        };

        int[] merged = mergeKArrays(arrays);

        System.out.print("Merged array: ");
        for (int value : merged) {
            System.out.print(value + " ");
        }
        System.out.println();
    }
}

Explanation of the Program

The HeapNode class is the key piece of bookkeeping. A plain min-heap of integers would only tell you the smallest value seen so far, not which array to pull the next element from, so each node carries three fields.

  • value: the element currently sitting at the front of one array.
  • arrayIndex: which of the k arrays this value came from.
  • elementIndex: the position of this value inside that array, used to find the next element once this one is consumed.
  • compareTo orders nodes by value using Integer.compare, which is what makes the PriorityQueue behave as a min-heap.
  • mergeKArrays seeds the heap with the first element of every non-empty array, then repeatedly polls the smallest node, writes its value into result, and pushes that array’s next element (if any) back onto the heap.

Step-by-Step Trace

Trace the algorithm on three fresh arrays, A = [2, 8], B = [1, 9, 12], and C = [5, 6], which should merge into [1, 2, 5, 6, 8, 9, 12].

IterationValue polledSource arrayNext element pushedResult so far
11B9 (B[1])[1]
22A8 (A[1])[1, 2]
35C6 (C[1])[1, 2, 5]
46Cnone, C exhausted[1, 2, 5, 6]
58Anone, A exhausted[1, 2, 5, 6, 8]
69B12 (B[2])[1, 2, 5, 6, 8, 9]
712Bnone, B exhausted[1, 2, 5, 6, 8, 9, 12]

At the end of each iteration, the heap holds exactly one still-unconsumed element from every array that has not yet been fully drained, and result holds every element removed so far in sorted order.

Examples

The two examples below use their own inputs, separate from the trace and the main method, so you can see the merge behave on different shapes of data.

Example 1: Merging Three Arrays of Equal Length

Three arrays of three elements each, with their smallest values spread across different positions, merge cleanly into one sorted array of nine elements.

Java
int[][] arrays = {
    {7, 15, 22},
    {3, 11, 29},
    {1, 4, 6}
};

int[] merged = mergeKArrays(arrays);
System.out.println(java.util.Arrays.toString(merged));
// Output: [1, 3, 4, 6, 7, 11, 15, 22, 29]

Example 2: Merging Arrays That Include an Empty Array

One of the three input arrays is empty. Because mergeKArrays only seeds the heap from arrays with length > 0, the empty array is simply skipped, and the remaining two arrays merge as usual.

Java
int[][] arrays = {
    {10, 20},
    {},
    {5, 15, 25}
};

int[] merged = mergeKArrays(arrays);
System.out.println(java.util.Arrays.toString(merged));
// Output: [5, 10, 15, 20, 25]

Common Mistakes to Avoid

Most bugs in this problem come from mishandling the bookkeeping around which array a heap value belongs to, not from the heap itself.

  • Pushing arrays[i][0] without checking length – seeding the heap from an empty array throws ArrayIndexOutOfBoundsException immediately. Guard the seed loop with arrays[i].length > 0 before reading index 0.
  • Comparing arrays with a linear scan instead of a heap – repeatedly scanning all k array fronts for the minimum works but costs O(n * k) instead of O(n log k). Use a PriorityQueue so each extraction is O(log k).
  • Forgetting to store elementIndex in the heap node – storing only the value and the array index loses the position inside that array, so you can’t find the next element to push. Track elementIndex alongside value and arrayIndex.
  • Pushing every element of every array upfront – inserting all n elements into the heap at once wastes memory and heap operations when only k elements ever need to be in the heap at the same time. Push one element per array at a time, replacing a value only after it’s consumed.
  • Implementing compareTo as value subtraction – this.value - other.value can silently overflow for values near Integer.MIN_VALUE or Integer.MAX_VALUE, producing an incorrectly ordered heap. Use Integer.compare(this.value, other.value) instead.

Edge Cases to Test

Interviewers watch for candidates who mention boundary inputs before being asked, so walk through these before you start coding.

  • Empty outer array (k = 0)
  • One or more sub-arrays empty
  • Single array only
  • All sub-arrays of length 1
  • Duplicate values across different arrays
  • Sub-arrays of very unequal lengths
  • Integer.MIN_VALUE / Integer.MAX_VALUE present
  • Null sub-array reference

Additional Considerations

The heap-based merge runs in O(n log k) time, where n is the total element count and k is the number of arrays: every one of the n elements is pushed and popped exactly once, and each heap operation costs O(log k) because the heap never holds more than k nodes at a time. Space usage is O(n) for the result array plus O(k) for the heap itself.

A null sub-array reference deserves special attention: calling arrays[i].length on a null entry throws NullPointerException before the heap logic ever runs, so validate or filter null entries up front if the input isn’t guaranteed to be clean. An alternative to the heap is pairwise divide-and-conquer merging, repeatedly merging arrays two at a time; it has the same O(n log k) complexity but trades the heap for recursive calls and temporary arrays, which can be easier to reason about when k is small.

Interview Follow-up Questions

Once you’ve implemented the base solution, expect an interviewer to push on how it generalizes.

  • What if the arrays are sorted in descending order instead of ascending? – swap the min-heap for a max-heap by reversing the comparator; the rest of the algorithm is unchanged.
  • What if you need to merge k sorted linked lists instead of arrays? – store a reference to the current node in each heap entry instead of an array index and position, and advance to node.next after polling.
  • What if the arrays are too large to fit in memory together? – stream each array from disk with a small read-ahead buffer per array, feeding the heap only the current front element of each buffer, similar to an external merge sort.
  • What if you need to parallelize the merge across multiple threads? – pair up arrays and merge each pair independently in parallel, then repeat on the merged results; this is the same divide-and-conquer idea used in parallel merge sort.

Conclusion

Merging k sorted arrays is a good test of whether you reach for a heap instead of brute-force sorting once you notice the inputs are already ordered. The HeapNode pattern used here, tracking a value alongside where it came from, shows up again in k-way merges of linked lists, files, and streams, so it’s worth internalizing rather than memorizing.

Try adapting the program to merge descending arrays or k linked lists as practice. You can learn more about array-based problems like this one on dailyjavaconcept.com: Arrays.