What Is a Sorted Run? The Merge Step Between Two Halves
A sorted run is a slice that is already in order. Merge sort's merge step takes two runs and writes one, using a pointer on each.
A sorted run is a contiguous slice whose values are already in order. Merge sort creates runs by sorting halves, then merges them. The merge is worth practicing on its own, before the recursion.
How it works
Put a pointer on each run. Compare the two heads. Write the smaller one to the result and advance that pointer. When one run is empty, append the rest of the other. Each element is written once, so merging n elements is O(n). The result is a new array. The inputs stay as they were.
Merge sort does this after each pair of recursive calls. The split is about log n levels deep, and each level merges n elements in total, so the sort is O(n log n). The extra arrays are O(n) memory. Bubble sort never builds a run on purpose. It swaps neighbours until order appears, and that is O(n²).
Press Run to execute this example. Use console.log to print a value.
Expected output: [1, 2, 3, 4, 8, 9]. Once the left run is exhausted, the remaining 9 can be copied without another comparison.
Worked example
The head comparisons are 1 versus 2, 4 versus 2, 4 versus 3, 4 versus 9, and 8 versus 9. They contribute [1, 2, 3, 4, 8]; the untouched right tail contributes [9].
Why it is correct
Before every comparison, merged is sorted and contains exactly the consumed prefixes of both runs. Because each run is sorted, the smaller head is the smallest remaining value anywhere, so copying it preserves the invariant. Once a run is empty, the other tail is already sorted and no smaller unwritten value exists. Appending it completes a sorted result containing every input value once.
Cost
Each pointer advances only forward, at most once per value. Merging lengths a and b therefore takes O(a + b) time and O(a + b) result space. The input runs are not mutated. Stability comes from taking the left head when values are equal.
In the course
Merge sort asks you to merge two sorted runs before you write the full sort. The next lesson contrasts that with bubble sort and with a scan that only checks whether a run is already sorted. A compare function still matters if you later call the built-in sort on numbers.
Common mistakes
Calling the built-in sort on a half, which skips the merge the lesson is teaching.
Forgetting to append the leftover run. The result then drops every value that was sitting behind the pointer that finished first.
Comparing the heads as strings. Numeric order is <= on the numbers, not the default string sort.
When to use it
Use a merge of two runs when both sides are already sorted and you need one sorted array. It is also the inner step of sorting a linked list, where random access is expensive and runs are natural.
When not to
Do not merge unsorted slices and expect a sorted result. The smaller-head rule is only true when each side is a run.
Problem-solving checklist
Verify both inputs are already sorted. State what each pointer means and why everything before it is finished. Test one empty run, unequal lengths, duplicates, and values that all come from one side first. Check that the leftovers are copied.
Optional enrichment
Merge records with a typed comparison function. Preserve left-before-right order for equal keys, then demonstrate stability with two records that have the same score but different names.