Merge K Sorted Lists
In this page:
Problem Idea
This problem asks you to combine k separate sorted lists into one fully sorted list — a generalization of the simpler two-list merge, where naively comparing across all k lists at every step would be needlessly slow.
Example: Problem Idea
#include <iostream>
using namespace std;
int main() {
int lists[3][2] = {{1, 4}, {2, 5}, {3, 6}};
cout << "Merging 3 sorted lists into one fully sorted output, not just two at a time";
return 0;
}public class Main {
public static void main(String[] args) {
int[][] lists = {{1, 4}, {2, 5}, {3, 6}};
System.out.println("Merging 3 sorted lists into one fully sorted output, not just two at a time");
}
}lists = [[1, 4], [2, 5], [3, 6]]
print("Merging 3 sorted lists into one fully sorted output, not just two at a time")#include <stdio.h>
int main() {
int lists[3][2] = {{1, 4}, {2, 5}, {3, 6}};
printf("Merging 3 sorted lists into one fully sorted output, not just two at a time");
return 0;
}Login to try C/C++/Java code in the editor
Heap Approach
A min heap solves this efficiently by holding just one candidate value from each of the k lists at a time — the current front of each list — so the overall smallest next value across all lists is always available at the heap's root.
Example: Heap Approach
#include <iostream>
#include <queue>
using namespace std;
int main() {
vector<vector<int>> lists = {{1, 4}, {2, 5}, {3, 6}};
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> heap;
for (int i = 0; i < 3; i++) heap.push({lists[i][0], i});
cout << "Heap holds one front value per list, smallest overall on top: " << heap.top().first;
return 0;
}import java.util.PriorityQueue;
public class Main {
public static void main(String[] args) {
int[][] lists = {{1, 4}, {2, 5}, {3, 6}};
PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
for (int i = 0; i < 3; i++) heap.add(new int[]{lists[i][0], i});
System.out.println("Heap holds one front value per list, smallest overall on top: " + heap.peek()[0]);
}
}import heapq
lists = [[1, 4], [2, 5], [3, 6]]
heap = [(lists[i][0], i, 0) for i in range(3)]
heapq.heapify(heap)
print(f"Heap holds one front value per list, smallest overall on top: {heap[0][0]}")#include <stdio.h>
int main() {
int lists[3][2] = {{1, 4}, {2, 5}, {3, 6}};
int minVal = lists[0][0], minList = 0;
for (int i = 1; i < 3; i++) if (lists[i][0] < minVal) { minVal = lists[i][0]; minList = i; }
printf("Heap holds one front value per list, smallest overall on top: %d", minVal);
return 0;
}Login to try C/C++/Java code in the editor
Process Minimum
Each step removes the minimum from the heap, appends it to the output, and then pushes the next value from whichever list that minimum came from — this keeps exactly one value per still-active list in the heap at all times.
Example: Process Minimum
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main() {
vector<vector<int>> lists = {{1, 4}, {2, 5}, {3, 6}};
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> heap;
vector<int> idx(3, 0);
for (int i = 0; i < 3; i++) heap.push({lists[i][0], i});
vector<int> output;
while (!heap.empty()) {
auto [val, li] = heap.top(); heap.pop();
output.push_back(val);
idx[li]++;
if (idx[li] < (int)lists[li].size()) heap.push({lists[li][idx[li]], li});
}
for (int v : output) cout << v << " ";
return 0;
}import java.util.PriorityQueue;
public class Main {
public static void main(String[] args) {
int[][] lists = {{1, 4}, {2, 5}, {3, 6}};
int[] idx = {0, 0, 0};
PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
for (int i = 0; i < 3; i++) heap.add(new int[]{lists[i][0], i});
StringBuilder out = new StringBuilder();
while (!heap.isEmpty()) {
int[] top = heap.poll();
out.append(top[0]).append(" ");
idx[top[1]]++;
if (idx[top[1]] < lists[top[1]].length) heap.add(new int[]{lists[top[1]][idx[top[1]]], top[1]});
}
System.out.println(out.toString().trim());
}
}import heapq
lists = [[1, 4], [2, 5], [3, 6]]
heap = [(lists[i][0], i, 0) for i in range(3)]
heapq.heapify(heap)
output = []
while heap:
val, li, ei = heapq.heappop(heap)
output.append(val)
if ei + 1 < len(lists[li]):
heapq.heappush(heap, (lists[li][ei + 1], li, ei + 1))
print(*output)#include <stdio.h>
int main() {
int lists[3][2] = {{1, 4}, {2, 5}, {3, 6}};
int idx[3] = {0, 0, 0}, output[6], n = 0;
for (int step = 0; step < 6; step++) {
int minVal = 1000000, minList = -1;
for (int i = 0; i < 3; i++)
if (idx[i] < 2 && lists[i][idx[i]] < minVal) { minVal = lists[i][idx[i]]; minList = i; }
output[n++] = minVal;
idx[minList]++;
}
for (int i = 0; i < n; i++) printf("%d ", output[i]);
return 0;
}Login to try C/C++/Java code in the editor
Complexity
With k lists and n total values across all of them, this heap-based approach runs in O(n log k) time, since each of the n values triggers one O(log k) heap operation — far better than repeatedly merging lists pairwise, which costs more comparisons overall.
Example: Complexity
#include <iostream>
using namespace std;
int main() {
cout << "Merge k sorted lists: O(n log k) time with n total values, O(k) heap space";
return 0;
}public class Main {
public static void main(String[] args) {
System.out.println("Merge k sorted lists: O(n log k) time with n total values, O(k) heap space");
}
}print("Merge k sorted lists: O(n log k) time with n total values, O(k) heap space")#include <stdio.h>
int main() {
printf("Merge k sorted lists: O(n log k) time with n total values, O(k) heap space");
return 0;
}Login to try C/C++/Java code in the editor
Practice
The core discipline is keeping the output correctly sorted at every step by always pulling the true global minimum next, which is exactly what the min heap guarantees without needing to compare across all k lists directly on each step.
Example: Practice
#include <iostream>
using namespace std;
int main() {
cout << "Always pull the true global minimum next -- that discipline is what keeps output sorted";
return 0;
}public class Main {
public static void main(String[] args) {
System.out.println("Always pull the true global minimum next -- that discipline is what keeps output sorted");
}
}print("Always pull the true global minimum next -- that discipline is what keeps output sorted")#include <stdio.h>
int main() {
printf("Always pull the true global minimum next -- that discipline is what keeps output sorted");
return 0;
}Login to try C/C++/Java code in the editor
Chapter Quiz — Complete all 5 topics to unlock
0/5 topics done
Complete these topics first: