Full lesson preview

Merge k sorted arrays

Merge k sorted lists of integers into one sorted list efficiently.

Python practice16 minSearching & SortingIntermediateLast updated March 25, 2026

Problem statement

You are given k sorted lists (each in non-decreasing order). Merge them into one sorted list and return it. Aim for an efficient solution that runs faster than concatenating and sorting all elements when possible (hint: use a min-heap for an optimal k-way merge). The input may include empty lists and negative numbers.

Task

Implement a function that merges k sorted arrays/lists into a single sorted list with good time complexity.

Examples

Merge three lists

Input

merge_k_sorted([[1,4,7],[2,5,8],[3,6,9]])

Output

[1, 2, 3, 4, 5, 6, 7, 8, 9]

All three sorted lists are merged into a single sorted list.

Input format

A list of k lists, each list sorted in non-decreasing order (e.g. [[1,3],[2,4]]).

Output format

A single list with all elements from the input lists in non-decreasing order.

Constraints

- Do not use a single call to sorted on the concatenation unless necessary. - Prefer O(N log k) complexity where N is total number of elements and k is number of lists. - You may use Python's heapq from the standard library.

Samples

Sample 1

Input

[[1, 4], [2, 3]]

Output

[1, 2, 3, 4]

Two sorted lists are merged into one sorted list.