What is the time and space complexity of Merge k Sorted Lists?

Time complexity: O(N log k). Space complexity: O(log k).

Merge k Sorted Lists

Hard

Concept

Code

Loading editor...

Tap Analyze to see visualization

Click Analyze to visualize

See step-by-step execution, variables, and output

Variables

Run code to see variables

Output

Console output will appear here

Press Space to start•← → to step•? all shortcuts

Solution Guide: Merge k Sorted Lists

Approach

Use iterative divide and conquer. Merge pairs of adjacent lists in each round, doubling the interval each time. This reduces k lists to 1 in O(log k) rounds. Each round processes all N total nodes once via the two-list merge.

Complexity Analysis

Time: O(N log k)
Space: O(log k)

Pattern

Linked List (Divide & Conquer Merge)

Why It Works

Merging pairs halves the number of lists each round, giving log k rounds. Each round touches all N nodes exactly once. This is more efficient than merging one list at a time, which would be O(N*k).

Updated Mar 2026