Skip to content
Tutorials Center
My learning

Topics

Lesson 81 of 225 ยท Sorting

Merge Sort

Learn merge sort in Python: split, sort and merge, with traces, top-down and bottom-up versions, O(n log n) analysis, stability, extra space and counting inversions.

Bubble, selection and insertion sort all take O(nยฒ) time. For 100,000 items that is around ten billion steps. Merge sort brings it down to O(n log n), about 1.7 million comparisons for the same input. It does this with a beautiful idea called divide and conquer: split the list in half, sort each half, and merge the two sorted halves into one sorted list.

Merge sort is also the first sorting algorithm in this chapter with a guaranteed O(n log n) running time, whatever the input looks like, and it is stable. Its price is O(n) extra memory. It is the backbone of Python's own Timsort, of sorting linked lists, and of sorting data that is too big for memory. In this lesson you will build it top-down and bottom-up, trace it, prove its running time with a recurrence, and use a small twist of the merge step to count inversions.

The idea

TEXT
                 [38, 27, 43, 3, 9, 82, 10]
                 /                        \
        [38, 27, 43, 3]               [9, 82, 10]          split
         /          \                  /        \
    [38, 27]      [43, 3]          [9, 82]     [10]
     /    \        /    \           /   \
  [38]  [27]    [43]   [3]       [9]   [82]
     \    /        \    /           \   /
    [27, 38]      [3, 43]          [9, 82]     [10]        merge
         \          /                  \        /
       [3, 27, 38, 43]                [9, 10, 82]
                 \                        /
              [3, 9, 10, 27, 38, 43, 82]
  1. Divide: split the list into two halves.
  2. Conquer: sort each half recursively. A list of 0 or 1 items is already sorted (the base case).
  3. Combine: merge the two sorted halves.

All the real work happens in step 3, so let us study it first.

Merging two sorted lists

Given two sorted lists, the smallest item overall must be one of the two front items. Compare the fronts, take the smaller one, and advance in that list. Repeat until one list is empty, then copy the rest of the other.

TEXT
left  = [3, 27, 38, 43]      right = [9, 82]
          ^                           ^
take 3  (3 < 9)      -> out = [3]
take 9  (27 > 9)     -> out = [3, 9]
take 27 (27 < 82)    -> out = [3, 9, 27]
take 38              -> out = [3, 9, 27, 38]
take 43              -> out = [3, 9, 27, 38, 43]
left is empty: copy the rest of right: 82

Each comparison places one item, so merging lists of total length m takes at most m - 1 comparisons: O(m) time.

Python The merge step

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The condition left[i] <= right[j] is what makes merge sort stable: when two items are equal, the one from the left half (which came earlier in the original list) goes first.

Top-down merge sort

Now the recursion is short. Print the splits and merges to see the picture above come alive.

Python Top-down merge sort with a trace

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

This version returns a new list and slices the input, which creates copies (items[:mid]). It is the clearest form. A production version sorts index ranges of one shared array and reuses a single helper buffer.

Why is it O(n log n)?

Merging a list of length m costs about m. Let T(n) be the time to sort n items:

TEXT
T(n) = 2 * T(n / 2) + n        (two half-size sorts, plus one merge)
T(1) = 1

Look at the recursion tree level by level:

TEXT
level 0:  1 merge  of n items               -> n work
level 1:  2 merges of n/2 items each        -> n work
level 2:  4 merges of n/4 items each        -> n work
...
level k:  2^k merges of n/2^k items each    -> n work

The sizes halve every level, so there are about log2(n) levels, and every level does about n work in total. Therefore the time is O(n log n) in the best, average and worst case. (The recurrences lesson shows the general method.)

Space: the merges need an output buffer of up to n items, and the recursion is log n deep, so the extra space is O(n).

Time Extra space Stable In-place
Merge sort O(n log n) always O(n) yes no (for arrays)
Python Counting merge sort comparisons

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The comparisons stay below n log2(n) (43,978 against 49,152 for 4,096 items, because merges often end early) and are tiny next to nยฒ / 2. Already-sorted and reversed inputs of 4,096 items both cost exactly 24,576 comparisons: 12 levels times 2,048, since each merge ends as soon as one half is used up. That is the contrast with insertion sort: merge sort has no bad inputs, but no great ones either.

Bottom-up merge sort (no recursion)

Top-down starts from the whole list and splits. Bottom-up goes the other way: treat every item as a sorted run of length 1, merge neighbouring runs into runs of length 2, then 4, 8, and so on, until one run covers everything. There is no recursion, so there is no risk of a deep call stack, and it maps nicely to how external sorting works (see parallel and external algorithms).

TEXT
width 1:  [5] [2] [8] [1] [9] [3]
width 2:  [2 5] [1 8] [3 9]
width 4:  [1 2 5 8] [3 9]
width 8:  [1 2 3 5 8 9]
Python Bottom-up merge sort

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

It allocates two arrays once and alternates between them, which avoids creating many small lists.

Counting inversions

An inversion is a pair of positions i < j with items[i] > items[j]: a pair that is out of order. The number of inversions measures how unsorted a list is (0 for sorted, n(n - 1) / 2 for reversed). Counting them by checking all pairs takes O(nยฒ).

Merge sort can do it in O(n log n) with one extra line. During a merge, when we take an item from the right half while k items are still waiting in the left half, that right item is smaller than all k of them. Those are k inversions found at once.

TEXT
left = [3, 27, 38, 43]   right = [9, 82]
take 3 (left)
take 9 (right) -> 27, 38, 43 still waiting in left: 3 inversions (27>9, 38>9, 43>9)
take 27, 38, 43 (left)
take 82 (right) -> nothing waits in left: 0 inversions
Python Counting inversions: brute force and merge sort

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both methods agree. This trick appears in interview problems ("count smaller numbers to the right", "reverse pairs") and in measuring how far two rankings differ.

Variant: three-way merge sort

Nothing says you must split in two. Three-way merge sort cuts the list into three parts, sorts each recursively and merges all three at once. The recursion is shallower: about log base 3 of n levels instead of log base 2.

That sounds like a win, but it is not. Each step of a three-way merge has to find the smallest of up to three fronts, which costs up to two comparisons per output item, so the total is about 2 n log3 n = 1.26 n log2 n comparisons. Two-way merging does 1 comparison per output item at log2 n levels. Fewer levels, more work per level: the O(n log n) class stays the same and the constant gets slightly worse.

Python Two-way versus three-way merge sort: counting comparisons

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

On 5,000 random numbers the two-way version used about 55,000 comparisons (close to n log2 n) and the three-way version about 68,000. Higher fan-out merging does pay off in one place: external sorting of files on disk, where the cost is the number of passes over the data, not the number of comparisons. A k-way merge with a heap reads the data fewer times.

Variant: merging in place with the gap method

Standard merging needs an O(n) buffer. Can you merge two sorted runs inside the list with O(1) extra space? Yes, with a trick borrowed from Shell sort: the gap method.

Treat the two runs as one range of length m. Start with a gap of ceil(m / 2). Compare every pair of items that are gap positions apart and swap if they are out of order. Then halve the gap (rounding up) and sweep again, until a gap-1 sweep finishes. Large gaps move big items far right and small items far left in one swap; the last sweeps clean up what is left.

TEXT
runs: [1 5 9 10 15 20] [2 3 8 13]     m = 10
gap 5: compare (1,20) (5,2) (9,3) (10,8) (15,13); four of the five pairs swap
gap 3, gap 2, gap 1: each sweep fixes what is left, and the final gap-1 sweep ends the merge
Python Merge two sorted runs without a buffer

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The price is time: the merge takes O(m log m) instead of O(m), so a merge sort built on it runs in O(n logยฒ n). It is also not stable, because swaps jump over equal items. Use it when memory is the hard limit and stability does not matter; otherwise a buffer is cheaper and simpler.

Merge sort in practice

  • Linked lists. Merging needs no extra array, because you only rewire pointers, and finding the middle is easy with fast and slow pointers. Merge sort is the best way to sort a linked list.
  • Huge files. Sort chunks that fit in memory, write them out, and merge the chunks (an external sort). See merging K sorted lists.
  • Stability. When you need equal items to keep their order and a guaranteed time bound.
  • Python. sorted() is Timsort, a merge sort that first finds existing sorted runs. heapq.merge merges already sorted iterables lazily.
  • Arrays in memory where space is tight: prefer heap sort or quick sort.

Common mistakes

  • Merging with < instead of <= on the left comparison, which swaps equal items and breaks stability.
  • Forgetting to copy the leftover items after the main loop.
  • Slicing in every recursive call and thinking it is free: items[:mid] copies the items. The clear version is fine for learning, but a tuned version sorts index ranges of one shared array.
  • Splitting with mid = len(items) // 2 but forgetting the base case len <= 1, which recurses forever on a one-item list.
  • Believing merge sort is in-place. The standard array version is not.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What is the time complexity of merge sort in the worst case?

    There are about log2(n) levels of splitting and each level merges n items in total, so merge sort is O(n log n) for every input.
  2. 2. How many comparisons does merge(left, right) make at most, if the two lists have 4 and 3 items?

    Each comparison places one item into the output, and when the last item remains no comparison is needed, so merging m items takes at most m - 1 = 6 comparisons.
  3. 3. Which line makes the merge step stable?

    Items in the left half come earlier in the original list. Taking the left one on ties keeps equal items in their original order.
  4. 4. In the inversion-counting merge, how many inversions are added when an item from the right half is taken while 3 items remain in the left half?

    The right item is smaller than the front of the left half, and the left half is sorted, so it is smaller than all 3 remaining left items. That is 3 inversions.
  5. 5. What is the extra space used by array-based merge sort?

    Merging needs an output (or helper) buffer as large as the part being merged, up to n items. The recursion stack adds only O(log n).

Summary

  • Merge sort splits the list in half, sorts both halves recursively and merges them.
  • Merging two sorted lists takes O(m) time by repeatedly taking the smaller front item.
  • Time is O(n log n) in every case (recurrence T(n) = 2T(n/2) + n); extra space is O(n).
  • It is stable when the merge takes from the left on ties, but not in-place for arrays.
  • The bottom-up version merges runs of width 1, 2, 4, ... without recursion.
  • Three-way merge sort has a shallower recursion but about 26% more comparisons; in-place merging with the gap method uses O(1) extra space at O(n logยฒ n) total time and loses stability.
  • Counting the left items still waiting whenever a right item is taken gives the number of inversions in O(n log n).

Next: Quick Sort