Sorting Tested code in 3 languages

Merge Sort, Visualized Step by Step

Split the array in half until every piece holds one value, then merge the pieces back together in order. Press play to watch every split, comparison and write, next to the exact line of code that runs.

Crio.Do · Last updated 18 November 2026

Interactive merge sort

Sort indices 0–7 (8 values).

0Comparisons
0Writes
1/–Step
def merge_sort(a, lo=0, hi=None):    if hi is None:        hi = len(a) - 1    if lo >= hi:        return    mid = (lo + hi) // 2    merge_sort(a, lo, mid)    merge_sort(a, mid + 1, hi)    merge(a, lo, mid, hi)  def merge(a, lo, mid, hi):    left = a[lo:mid + 1]    right = a[mid + 1:hi + 1]    i = j = 0    k = lo    while i < len(left) and j < len(right):        if left[i] <= right[j]:            a[k] = left[i]            i += 1        else:            a[k] = right[j]            j += 1        k += 1    while i < len(left):        a[k] = left[i]        i += 1        k += 1    while j < len(right):        a[k] = right[j]        j += 1        k += 1

The highlighted line is the one the animation is running. This is the exact code we test.

Tip: use the arrow keys to step when the visualizer has focus. Try duplicates, a sorted list or your own numbers.

On this page
  1. How it works
  2. Worked example
  3. Complexity
  4. When to use it
  5. Common mistakes
  6. Interview questions
  7. FAQ
  8. Sources

How merge sort works

Merge sort is a divide-and-conquer sort built on one easy skill: merging two lists that are already sorted. Look at the front of both, take the smaller one, repeat. One pass is enough, because you never have to look back.

Picture two sorted piles of exam papers, lowest mark on top. To make one sorted pile, keep taking whichever top paper has the lower mark. Merge sort gets its sorted piles by splitting the array in half, and in half again, until every piece holds one value. A single value is always sorted, so the merging can start.

This page uses the top-down version with inclusive bounds. Each merge copies the two halves into temporary arrays, then writes values back into the original array from left to right. The comparison is left[i] <= right[j]: on a tie it takes from the left half, so equal values keep their original order. That property is called stability.

The counters show writes instead of swaps, because merge sort never swaps. Each level of splitting writes every value back once, so the number of writes is about n × log₂ n whatever the input looks like. Only the number of comparisons changes with the data.

The algorithm in 5 steps

  1. 1 If the range holds one value, it is sorted: return.
  2. 2 Split it at mid = (lo + hi) // 2.
  3. 3 Sort the left half, then the right half, the same way.
  4. 4 Copy both sorted halves aside.
  5. 5 Write the smaller front value back each time; when one half runs out, copy the rest of the other.

Worked example

Here is the full run on a fixed array, generated by the same code as the visualizer. The table shows every split and every finished merge; the individual comparisons and writes inside each merge are counted in the total but not listed.

Input: [38, 27, 43, 3, 9, 82, 10]

  1. Step 2 Split indices 0–6 in the middle: sort indices 0–3, then indices 4–6. 382743398210
  2. Step 3 Split indices 0–3 in the middle: sort indices 0–1, then indices 2–3. 382743398210
  3. Step 4 Split indices 0–1 in the middle: sort index 0, then index 1. 382743398210
  4. Step 11 Indices 0–1 are now sorted: 27, 38. 273843398210
  5. Step 12 Split indices 2–3 in the middle: sort index 2, then index 3. 273843398210
  6. Step 19 Indices 2–3 are now sorted: 3, 43. 273834398210
  7. Step 28 Indices 0–3 are now sorted: 3, 27, 38, 43. 327384398210
  8. Step 29 Split indices 4–6 in the middle: sort indices 4–5, then index 6. 327384398210
  9. Step 30 Split indices 4–5 in the middle: sort index 4, then index 5. 327384398210
  10. Step 37 Indices 4–5 are now sorted: 9, 82. 327384398210
  11. Step 45 Indices 4–6 are now sorted: 9, 10, 82. 327384391082
  12. Step 60 Indices 0–6 are now sorted: 3, 9, 10, 27, 38, 43, 82. 391027384382

Total for this run: 14 comparisons and 20 writes, in 61 animation steps. Result: 3, 9, 10, 27, 38, 43, 82.

Time and space complexity

Best

O(n log n)

The split is always in the middle, whatever the data, so there are ⌈log₂ n⌉ levels with n writes each. Sorted input only saves comparisons.

Average

O(n log n)

Same structure on every input: log n levels, each merging n values in one pass.

Worst

O(n log n)

No input can unbalance the splits, which is why merge sort is used when a guarantee matters.

Space

O(n)

Merging needs temporary room for the halves, plus O(log n) for the recursion stack.

Stable:
Yes
In place:
No
Style:
Top-down
Tie rule:
Take left (<=)

On the 8 numbers in the visualizer above, quick sort makes 38 comparisons and 5 swaps; merge sort makes 16 comparisons and 24 writes on the same array. Counts like these depend on the input and the exact variant, which is why complexity is stated as growth (Big O), not as exact numbers.

When to use it, and when not to

Good fit

  • You need a stable sort, for example sorting orders by date after sorting them by customer, without scrambling the first order.
  • You need guaranteed O(n log n) time, whatever the input.
  • Linked lists: merging only relinks nodes, so it needs no extra array, and no random access is required.
  • Data that does not fit in memory: sort chunks that fit, write them to disk, then merge the sorted chunks (external sorting).

Pick something else when

  • Memory is tight and you are sorting a large array: the O(n) buffer may hurt. An in-place sort like heap sort or quick sort fits better.
  • Very small arrays: insertion sort is faster on a handful of values, which is why library hybrids like Timsort use it for short runs.

Common mistakes and bugs

  1. 1.Writing < instead of <= in the merge

    The output is still sorted, but on ties it now takes from the right half first, so equal values swap order and the sort is no longer stable. The bug stays invisible until someone relies on stability.

  2. 2.Forgetting the leftover loops

    When one half runs out, the rest of the other half still has to be copied back. Leave those two loops out and the last values of the range keep stale data.

  3. 3.Rounding mid up with inclusive bounds

    With mid = (lo + hi + 1) // 2 and recursion on (lo, mid), a two-element range calls itself on the same range forever. Round down, and recurse on (lo, mid) and (mid + 1, hi).

  4. 4.Allocating at every level

    Copying halves on every merge, as this teaching version does, allocates O(n log n) memory in total. Production code allocates one buffer of size n once and reuses it.

  5. 5.Trusting JavaScript's default sort with numbers

    JavaScript's sort() compares values as strings by default, so [10, 9, 1].sort() returns [1, 10, 9]. Pass a comparator: arr.sort((a, b) => a - b).

Interview questions

Try answering before you open the model answer.

Q1 Why is merge sort stable, and what would break that?

Model answer: When the two front values are equal, the merge takes the one from the left half first, and everything in the left half came earlier in the input. Changing <= to < takes from the right on ties, so equal values swap order and stability is lost.

Q2 Sort a linked list in O(n log n) time.

Model answer: Use merge sort. Find the middle with slow and fast pointers, split the list there, sort both halves recursively, and merge by relinking nodes. The merge needs no extra array; the recursion uses O(log n) stack, and a bottom-up version needs O(1) extra space.

Q3 Count the inversions in an array.

Model answer: Run merge sort and count during each merge. When you take a value from the right half while i values remain in the left half, that value forms an inversion with each of those remaining values, so add len(left) − i. The total runs in O(n log n).

Q4 How would you sort 100 GB of data with 4 GB of RAM?

Model answer: External merge sort. Read about 4 GB at a time, sort it in memory, and write it out as a sorted run: about 25 runs. Then do a k-way merge, reading each run in buffered blocks and using a min-heap to pick the smallest front value.

Q5 Merge sort or quick sort: which would you choose?

Model answer: For an in-memory array of numbers, quick sort or the library sort, since it is in place and fast in practice. Choose merge sort when stability matters, when you need a guaranteed O(n log n), for linked lists, or for data on disk.

Frequently asked questions

Is merge sort stable?

Yes, as long as the merge takes from the left half when two values are equal, which is what left[i] <= right[j] does. Equal values then come out in the same order they went in. Writing < instead of <= still sorts correctly but quietly breaks stability, a common interview follow-up.

Why does merge sort need extra memory?

Merging two halves of the same array in place would overwrite values you have not read yet. The simple fix is to copy the halves aside first and write the merged result back, which needs O(n) extra space. In-place merge algorithms exist, but they are complex and slower in practice.

What is the time complexity of merge sort?

O(n log n) in the best, average and worst case. The array is always split in the middle, giving about log₂ n levels, and each level merges all n values in a single pass. Already sorted input reduces the number of comparisons, but not the number of writes.

Is merge sort faster than quick sort?

Usually not on arrays in memory. Quick sort works in place and avoids copying, so it tends to win in practice. Merge sort has the better guarantees: O(n log n) on every input and stability. It is also the better fit for linked lists and for sorting data stored on disk.

What is the difference between top-down and bottom-up merge sort?

Top-down merge sort, shown here, splits recursively until pieces have one value, then merges on the way back up. Bottom-up merge sort skips recursion: it merges neighbouring runs of size 1, then 2, then 4, and so on. Both do O(n log n) work; bottom-up avoids the recursion stack.

Crio Software Development

Go from watching algorithms to using them

Crio's Software Development Fellowship has you practise data structures and algorithms by building real projects, the way they come up at work and in interviews. Start with a free trial session.

Explore the program

Free trial · No credit card required

Sources

  1. Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms (3rd ed., MIT Press, 2009)
    Section 2.3.1, the divide-and-conquer approach (merge sort).
  2. Sedgewick and Wayne, Algorithms (4th ed., Addison-Wesley, 2011)
    Section 2.2, Mergesort.
  3. Donald E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching (2nd ed., 1998)
    Section 5.2.4, Sorting by merging.

The animation, the worked example and the step counts are all generated by one implementation of merge sort, which is unit-tested against an independent version on edge cases and hundreds of random inputs. The Python, Java and JavaScript code is the exact code shown above, run on the same cases.

Last updated:

More algorithms, visualized

Every page runs real, tested code and lets you step through it with your own input.

All algorithms