cf.completefrontend
TWO POINTERS · FOUNDATION

Merging two sorted lists

Combine two sorted lists into one sorted list by always taking the smaller of the two front items.

Time O(n + m)Space O(n + m)8 practice problemsStep-through picture

The idea

You have two lists that are each sorted, like two feeds of messages ordered by time, and you need one list in order. You could join them and sort again, but that throws away the order you already have.

Merging keeps one index in each list: i for a and j for b. The smallest item not yet used must be a[i] or b[j], because each list is sorted. So compare those two, push the smaller one, and move that list's index forward. Repeat until one list runs out, then copy what is left of the other.

Each item is looked at once, so merging two lists of lengths n and m takes n + m steps. Merge sort is built on this step, and the same walk answers many questions about two sorted lists: shared items, the closest pair, overlapping time ranges.

An everyday example

Two lines merging at a ticket gate

Two queues of people, each ordered by ticket number, merge into one gate. The gate keeper looks only at the first person in each queue and lets in the one with the smaller ticket number. When one queue is empty, the rest of the other queue walks straight through, already in order.

How the example maps to the code
In the exampleIn the code
The first person in queue Aa[i]
The first person in queue Bb[j]
Letting the smaller ticket throughmerged.push(a[i]); i++
One queue is emptyi === a.length
The rest of the other queue walks throughwhile (j < b.length) merged.push(b[j++])

From the slow way to merging two sorted lists

  1. Start with the easy way: join the two lists with [...a, ...b] and call sort. It works, but it costs O((n + m) log(n + m)) and throws away the fact that each list is already sorted. Both lists did half the work for you, and the sort starts from scratch.
  2. Ask where the smallest item of both lists can be. Each list is sorted, so its smallest item is at its front. The smallest item overall must therefore be a[0] or b[0]. One comparison finds it.
  3. After you take that item, the same question repeats on what's left: the next smallest is at one of the two fronts again. Instead of removing items from the lists, which costs time with shift, keep an index into each one: i for the front of a and j for the front of b.
  4. When one list runs out, there is nothing left to compare. Every remaining item of the other list is already sorted and at least as big as everything taken so far, so copy them as they are. Compare the fronts, take the smaller, advance, then copy the leftovers: that loop is merging.

How it works

  1. Create an empty merged list and start i = 0 in a and j = 0 in b.
  2. While both lists still have items, compare a[i] with b[j].
  3. If a[i] <= b[j], push a[i] and move i forward.
  4. Otherwise push b[j] and move j forward.
  5. When one list runs out, push every item left in the other list.
  6. Return merged: it holds every item from both lists, in sorted order.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function mergeSorted(a, b) {
  2. const merged = [];
  3. let i = 0;
  4. let j = 0;
  5. while (i < a.length && j < b.length) {
  6. if (a[i] <= b[j]) {
  7. merged.push(a[i]);
  8. i++;
  9. } else {
  10. merged.push(b[j]);
  11. j++;
  12. }
  13. }
  14. while (i < a.length) merged.push(a[i++]);
  15. while (j < b.length) merged.push(b[j++]);
  16. return merged;
  17. }

How fast it is

TimeO(n + m)
Extra memoryO(n + m)

Each item from both lists is pushed exactly once, after at most one comparison. The new list holds all n + m items. Merging in place from the back needs O(1) extra memory.

  • Best caseO(n + m)

    Every item of a is smaller than b[0], like a = [1, 2] and b = [5, 9, 12]: only n comparisons, then b is copied. The pushes still cost n + m.

  • Average caseO(n + m)

    The lists interleave: about one comparison per item pushed.

  • Worst caseO(n + m)

    The lists alternate until the very end, so the main loop runs n + m - 1 comparisons. Each item is still pushed exactly once.

Common mistakes

  • Forgetting to copy the leftovers after the main loop. The biggest items of one list are silently lost.
  • Joining the lists and calling sort again. It works, but costs O(n log n) and ignores the order you were given.
  • Comparing numbers stored as strings. "10" < "9" is true, so convert with Number first.
  • When merging in place, filling from the front. The writes overwrite items of a that haven't been placed yet; fill from the back instead.

When to use it

Look for these clues in a problem:

  • You get two (or more) lists that are already sorted.
  • You need one sorted list, or something about both lists together: shared items, missing items, the closest pair.
  • Sorting the joined list again would work but the question hints at O(n + m) time.
  • The data is a stream you read from the front, such as two time-ordered logs.

Check yourself

Answer each one in your head first, then open it.

Why must the smallest remaining item be a[i] or b[j]?

Each list is sorted, so every item after a[i] is at least a[i], and every item after b[j] is at least b[j]. The smallest item overall is the smaller of the two fronts.

What happens if you change <= to <?

The result is still sorted, but on a tie the item from b goes first. Equal items from the two lists swap their relative order, so the merge is no longer stable.

How many comparisons can merging lists of 4 and 5 items need, at most?

8, which is 4 + 5 - 1. The last item never needs a comparison, because by then the other list is empty.

Why don't the leftover items need any comparisons?

They come from one sorted list, so they are in order among themselves, and each is at least as big as the last item pushed. Appending them keeps the result sorted.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 8 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The loop keeps one promise: merged holds exactly the i + j smallest items of both lists, in sorted order, and every item not yet taken is at least as big as the last item in merged. At the start, merged is empty, so the promise holds.

Each step keeps it. Every item left in a is at least a[i] and every item left in b is at least b[j], because both lists are sorted. So the smaller of a[i] and b[j] is the smallest item left anywhere. Pushing it adds the next smallest item, so merged stays sorted and complete.

The main loop ends when one list is used up, because each step moves i or j forward. The other list's leftovers are sorted and, by the promise, no smaller than anything in merged, so appending them in order keeps merged sorted. In the end it holds all n + m items.

Going deeper

3 more ideas

Why the smaller front item is always next

Every item left in a is at least a[i], because a is sorted. Every item left in b is at least b[j]. So the smallest item left anywhere is the smaller of a[i] and b[j]. Pushing it keeps merged sorted, and the rule holds again for the next step.

Why <= keeps equal items stable

When a[i] equals b[j], the code takes the item from a first. That means equal items from a always come before equal items from b. This property is called stable, and it matters when the items are objects sorted by one field, such as messages sorted by time: two messages with the same time keep the order of their lists.

Merging into the end of an array in place

If a has empty spots at the end that are big enough for b, you can merge without a new array by filling from the back. Put a write index at the last spot and compare the largest items, a[i] and b[j] at the ends, placing the larger one at the write index. Filling from the back never overwrites an a item that hasn't been placed yet.

Work it by hand

Every step in a table, with why

Merge two sorted lists that share the value 6 three times, so the tie rule matters, and where b has leftovers at the end.

a = [2, 6, 6, 11], b = [1, 6, 8, 15, 20]

Stepija[i]b[j]PushedWhat happensWhy
100211 from b2 <= 1 is false: take b[j]The smallest item overall is the front of b.
201262 from a2 <= 6: take a[i]Now the front of a is smaller.
311666 from aA tie: <= takes a firsta[1] and b[1] are both 6. Taking from a on a tie keeps the merge stable.
421666 from aAnother tie: a againa has a second 6, and it still goes before b's 6.
5311166 from b11 <= 6 is false: take b[j]Now b's 6 goes in, after both 6s from a.
6321188 from bTake b[j]8 is still smaller than 11.
733111511 from aTake a[i]; a is used upi becomes 4, equal to a.length, so the main loop ends after 7 comparisons.
843-1515 from bLeftover loop for bNo comparison needed: every leftover item of b is at least 11.
944-2020 from bLeftover loop endsj reaches b.length. The leftover loop for a never ran.

It returns [1, 2, 6, 6, 6, 8, 11, 15, 20]: 9 items after 7 comparisons. The trace ends when both lists are used up.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Merging two sorted listsO(n + m)O(n + m)Both lists are already sorted and you want a new sorted list, or you need to walk both in order.
Join, then sortO(n log n)O(n)The lists aren't sorted, or the code isn't hot and one line matters more than speed.
Merge in place from the backO(n + m)O(1)a already has empty slots at the end for b, and the question asks you not to create a new array.
Min-heap k-way mergeO(n log k)O(k)There are many sorted lists, such as k paged result sets, not just two.

Extra memory: O(n + m) for the new merged array. Merging into the end of a from the back, when a has room, needs only O(1) extra.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Merging two sorted lists and the other approaches, on a scale where each line up is 10 times more steps.
  • Merging two sorted lists, Merge in place from the back O(n + m)
  • Join, then sort, Min-heap k-way merge O(n log n)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Merging two sorted lists202,0002 million
Join, then sort339,96620 million
Merge in place from the back202,0002 million
Min-heap k-way merge339,96620 million

Inputs that need care

5 tricky inputs
One list empty: a = [], b = [3, 5]
The main loop never runs, the leftover loop copies b, and the result is [3, 5].
Both lists empty
All three loops are skipped and the result is [].
Equal values in both lists
<= takes the item from a first, so equal items keep their list order: all of a's copies, then all of b's. With <, b's copies would come first and the merge would not be stable.
Numbers stored as strings: a = ["9"], b = ["10"]
"10" <= "9" compares text and is true, so the result is ["10", "9"]. Convert with Number first.
Objects, like messages with a time field
Compare a[i].time <= b[j].time instead of the objects themselves. The same tie rule keeps messages with equal times in their list order.

Variations and follow-ups

Twists interviewers add

Merging in place from the back

If a has empty slots at the end big enough for b, start a write index at the last slot and compare the largest items, a[i] and b[j] at the ends. Place the larger one and move left. Filling from the back never overwrites an a item that hasn't been placed.

Merging many lists

For k sorted lists, keep the front item of each list in a min-heap. Pop the smallest, push it to the result, and push the next item from the same list. That is O(N log k) for N items in total.

Intersection and union

The same walk answers set questions on sorted lists. For items in both lists, push only when a[i] === b[j] and move both indexes. For the union without repeats, skip an item equal to the last one pushed.

Counting inversions

During merge sort's merge step, each time b[j] is taken before a[i], every item left in a is bigger than b[j]. Adding a.length - i counts how many pairs are out of order, in O(n log n) total.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "two sorted lists" or "two time-ordered streams" and a request for one sorted result, the common items, or the closest pair across both.
  • Explain the key fact first: "the smallest item left must be at one of the two fronts, because each list is sorted". Then the code is just that sentence in a loop.
  • Test by hand: one empty list, lists of very different lengths, and equal values in both lists. Forgetting the leftover loops is the most common bug, and the different-lengths test catches it.
  • The usual follow-up is "merge into a, which has room at the end, without a new array". The answer is to fill from the back, comparing the largest items, so no unplaced item of a is overwritten.

Where frontend code uses it

The same idea in real UI code
  • Combining two time-ordered feeds, such as messages from the server and messages typed while offline, into one timeline without sorting again.
  • Merging two sorted lists of search results or autocomplete suggestions that come from different sources.
  • Merge sort, which uses this step, is the classic stable sort. JavaScript engines have to sort stably for Array.prototype.sort, and V8 uses TimSort, which merges sorted runs in the same way.

Related algorithms