Where it runs
1. The problem
The sorts you wrote so far walk the list again and again. On a list of n items they make roughly n times n comparisons. For 100 items that is 10,000 comparisons, which is fine. For a million it is a trillion. You want a sort whose work grows much more slowly.
Start from a simple fact. Two lists that are already sorted are easy to combine into one sorted list. You look at the first numbers of both lists and take the smaller one, again and again. So if you already had two sorted halves, the job would be almost done.
Merge sort turns that fact into a full method. Split the list in half, sort each half, then merge the two sorted halves into one.
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includedmergeSort([5, 2, 4, 6, 1, 3])Sort [5, 2, 4, 6, 1, 3]. Merge sort cuts at the midpoint without looking at values, sorts each half, then merges them.
One operation is one comparison or one move. Every frame, each lane does the same number of operations, so the slow one falls behind.
O(n²)O(n log n)O(n log n)
Operations for n numbers, and roughly how long they take at 100 million simple operations a second. An estimate from the same count, not a measurement.
Recognise it
Say these words and it is this pattern
- sort an array of real size (thousands+)
- need O(n log n) guaranteed or expected
- sort as a subroutine before another algorithm (two pointers, greedy, sweep)
- stability required (merge sort) or in-place expected (quicksort)
- just "sort this" with no small-n or special-key hint
Looks similar, isn't
- Elementary sorts (selection, bubble, insertion)
Those never split the array and cost n squared. Splitting is what buys the log n.
- Non-comparison sort (counting / radix)
Counting and radix sort beat n log n by reading digits. They need keys in a small range.
- Binary heap / priority queue
Heap sort also runs in n log n and needs no buffer. It is slower in practice on real data.
- Recursion
Recursion is the mechanism these use, not the pattern. Where the cut goes is the real idea.
n up to 1e6 gives O(n log n). Merge sort needs O(n) extra memory, quick sort needs O(log n).
On LeetCode
Problems that need a sort that is O(n log n) on every input, a merge of two sorted lists, or a count of pairs taken while merging. Split in half, sort each half, and merge from the front.
The lesson's mergeSort passes, since it stays O(n log n) on every input.
Only the merge step, written from the back so nothing in nums1 is overwritten before it is read.
Sort both arrays, walk them together as in a merge, and keep the values that match.
Before each merge, count for every value on the left how many values on the right are less than half of it.