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.
- 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. - Seed the heap by inserting the first element of every non-empty array, along with its array index and element index 0.
- While the heap is not empty, remove the node holding the smallest value and append that value to the result array.
- 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.
- Repeat steps 3 and 4 until the heap is empty, at which point every element from every array has been moved into the result.
- Return the result array, which now holds all elements from all
karrays 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.
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 thekarrays this value came from.elementIndex: the position of this value inside that array, used to find the next element once this one is consumed.compareToorders nodes byvalueusingInteger.compare, which is what makes thePriorityQueuebehave as a min-heap.mergeKArraysseeds the heap with the first element of every non-empty array, then repeatedly polls the smallest node, writes its value intoresult, 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].
| Iteration | Value polled | Source array | Next element pushed | Result so far |
|---|---|---|---|---|
| 1 | 1 | B | 9 (B[1]) | [1] |
| 2 | 2 | A | 8 (A[1]) | [1, 2] |
| 3 | 5 | C | 6 (C[1]) | [1, 2, 5] |
| 4 | 6 | C | none, C exhausted | [1, 2, 5, 6] |
| 5 | 8 | A | none, A exhausted | [1, 2, 5, 6, 8] |
| 6 | 9 | B | 12 (B[2]) | [1, 2, 5, 6, 8, 9] |
| 7 | 12 | B | none, 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.
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.
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
ArrayIndexOutOfBoundsExceptionimmediately. Guard the seed loop witharrays[i].length > 0before reading index 0. - Comparing arrays with a linear scan instead of a heap – repeatedly scanning all
karray fronts for the minimum works but costsO(n * k)instead ofO(n log k). Use aPriorityQueueso each extraction isO(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
elementIndexalongsidevalueandarrayIndex. - Pushing every element of every array upfront – inserting all
nelements into the heap at once wastes memory and heap operations when onlykelements 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.valuecan silently overflow for values nearInteger.MIN_VALUEorInteger.MAX_VALUE, producing an incorrectly ordered heap. UseInteger.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.nextafter 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.



