Merge sort, from one page to a sorted shelf

Definition

Merge sort orders a list by splitting it into a left half and a right half, sorting each half by the same steps, and merging the two sorted halves into one sorted list. It solves the problem of arranging comparable items from smallest to largest. Splitting stops at a piece that holds one item, because that piece is already sorted.

Analogy

Picture a monastery shelf of unbound pages standing in the order 5, 2, 8, 1. The librarian splits that pile into two piles and tells each helper to split again, until every person holds a single page. A single page is already in order, so the splitting ends there. Helpers then sit in pairs and build a new pile. They look only at the front page of each pile and move the earlier page onto the new pile. If the two fronts are tied, they move the page from the left pile. When one pile runs out, the rest of the other pile goes on the end, already in order. Those new piles are merged the same way until one shelf remains, now reading 1, 2, 5, 8.

Each part of the picture is one part of the algorithm. The full shelf is the input list. Each split is the divide step. One page is a piece of length one, which is already sorted. The two front pages are the pair of values the merge compares. The new pile is the merged result. A round in which every page is placed once is one level of the sort. The number of rounds is the number of times the shelf can be halved.

The analogy breaks down in three places. A person can look past the front page and plan ahead; the merge looks only at the two fronts. The new pile needs a clear stretch of table as long as the pages being merged, and that stretch is the extra memory the algorithm uses, so the pages are copied rather than rearranged in the original space alone. The table also does not decide a tie by itself; the left-pile rule has to be stated, and that rule is what keeps equal items in their original order.

Before you start

• A list of items, and what it means for that list to be ordered from smallest to largest

• A function that calls itself, which is called recursion

• Reading a comparison such as less than or equal between two items

Level 1 · Beginner: Split until every piece has one item

Merge sort works on a piece by cutting it into a left half and a right half, sorting each half with the same steps, and merging the results. Solving two smaller copies of the same problem, then combining the answers, is called divide and conquer. The cutting stops when a piece holds one item, or none. A piece that small is already sorted, so the sort has a bottom.

Follow the list 5, 2, 8, 1 all the way down. The first cut falls between 2 and 8, leaving the pieces 5, 2 and 8, 1. Each piece is cut again. 5, 2 becomes the single items 5 and 2. 8, 1 becomes the single items 8 and 1. Every piece now holds one item. That is the same list, split until nothing remains to split.

The merges climb back up the same pieces. Merge 5 with 2. The fronts are 5 and 2, so 2 is placed first and 5 follows, giving 2, 5. Merge 8 with 1. The fronts are 8 and 1, so 1 is placed first and 8 follows, giving 1, 8. Now merge 2, 5 with 1, 8. The fronts are 2 and 1, so 1 is placed. The fronts are then 2 and 8, so 2 is placed. The fronts are then 5 and 8, so 5 is placed. The left piece is empty, so the remaining 8 is copied onto the end. The list is 1, 2, 5, 8.

The merge rule is small enough to memorize. Look only at the first remaining item of each half. Move the smaller one into the result. When the two fronts are equal, move the one from the left half. When one half runs out, copy the rest of the other half in the order it already has. Each half was sorted before this merge, so the combined result is sorted too. The copy of a leftover half is required: those items have not been placed yet.

This list of four items used two rounds of merging. The first round built the pairs 2, 5 and 1, 8. The second round built the full list. A list of eight items needs one more round, because one more halving is possible. In every round, each item is placed exactly once. Some of those placements copy a leftover tail and do not make a new comparison. Every placement looks at two fronts or at no fronts at all, so a round stays proportional to the length of the list. The number of rounds is the number of times that length can be halved.

The code below is that procedure and nothing more. merge_sort cuts the list at the midpoint, sorts the two slices, and returns what merge builds. A list of length zero or one is returned as a fresh copy. merge walks the two halves with indexes i and j, appends the chosen front, and extends the result with whichever tail remains. Running it on 5, 2, 8, 1 prints [1, 2, 5, 8] and leaves the original list unchanged.

def merge_sort(items):    if len(items) <= 1:        return list(items)    mid = len(items) // 2    left = merge_sort(items[:mid])    right = merge_sort(items[mid:])    return merge(left, right)def merge(left, right):    merged = []    i = 0    j = 0    while i < len(left) and j < len(right):        if left[i] <= right[j]:            merged.append(left[i])            i += 1        else:            merged.append(right[j])            j += 1    merged.extend(left[i:])    merged.extend(right[j:])    return mergedif __name__ == "__main__":    original = [5, 2, 8, 1]    result = merge_sort(original)    assert result == [1, 2, 5, 8]    assert original == [5, 2, 8, 1]    print(result)

Key takeaways

Cut the list in half until every piece holds one item; that piece is already sorted.

Merge by taking the smaller front, and take the left front when the two fronts are equal.

Copy the leftover tail after the other half becomes empty.

Each round places every item once, and the rounds are the number of times the length can be halved.

Level 2 · Intermediate: One buffer, and the cases at the edges

The beginner version builds a new list on every merge, which makes the data flow easy to see. The version below keeps one extra buffer, aux, of the same length as the input, and writes merged items back into a working list called source. merge_sort starts by copying the caller's list into source, so later writes cannot change the list the caller still holds. If that copy has length zero or one, it is already sorted and the function returns it. Otherwise it allocates aux and sorts the half-open range from index 0 up to, but not including, n. A half-open range is a start index lo together with an end index hi that points just past the last item. The number of items in the range is hi minus lo.

sort returns at once when hi minus lo is less than 2, because the range is empty or a single item. Otherwise it chooses the midpoint mid as lo plus half the width, written lo + (hi - lo) // 2. Adding lo and hi before the division can overflow a fixed-size integer in other languages, and the midpoint then lands outside the range. Python integers grow as needed, and this is still the form to copy into those languages. sort then sorts the range from lo to mid, sorts the range from mid to hi, and only then calls _merge. The right range starts at mid, so mid itself belongs to the right half and the two ranges share no index.

_merge begins by copying source[lo] through source[hi - 1] into aux. The later writes go back into source, and the copy means a write cannot destroy a value that has not been read yet. i starts at lo and walks the left half in the buffer, up to but not including mid. j starts at mid and walks the right half, up to but not including hi. For each output index k from lo up to hi, the code takes one of four branches, in this order. If i has reached mid, the left half is exhausted and the next item is aux[j]. If j has reached hi, the right half is exhausted and the next item is aux[i]. If aux[i] is less than or equal to aux[j], the next item is aux[i]. Otherwise the next item is aux[j]. The equal case takes the left item.

A sort is stable when two items that compare equal keep the order they had in the input. This merge is stable for a precise reason. Every item in the left half originally stood to the left of every item in the right half, because the halves are contiguous pieces of the list. Inside each half, the earlier merges already kept equal items in their original order; a single item, the base of those merges, has no pair that could be swapped. Walking a half from left to right keeps that internal order. Preferring the left half when the keys are equal keeps the earlier item ahead of the later one. Single items are stable, and a merge of two stable halves is stable, so every larger piece is stable. This style of argument, where the smallest case is checked and each larger case follows from smaller ones, is called induction.

The edge cases fall out of the same branches. An empty list returns before sort is called. A single item returns inside sort because the width is one. A length of three uses midpoint 1, so the left half has the first item and the right half has the other two; the extra item goes right because the midpoint is rounded down. Duplicates such as 4, 4, 4 stay in place because equality takes from the left. A reversed list and an already ordered list both finish ordered. In this version they do the same shape of work, because the merges run either way. The stability test needs items that compare by a key alone: Keyed holds a key and a label, and less-than-or-equal looks only at the key. Sorting key 1 labeled a, key 2 labeled b, and key 1 labeled c must yield labels a, c, b. If the merge had preferred the right side on a tie, c would have jumped ahead of a.

The tests at the bottom of the code check those cases and print ok when they pass. Read a failure as a claim about a branch. An empty-list failure means the early return copied nothing. A single-item failure means the width check used the wrong cutoff. An odd-length failure means the midpoint split is uneven in the wrong direction. A label failure means the comparison used a strict less-than that lets the right half win ties, or the halves were not merged left to right. After the tests pass, the next useful exercise is to point at each branch of _merge and name which test forces that branch to run.

class Keyed:    """An item whose order depends only on key, so labels can test stability."""    def __init__(self, key, label):        self.key = key        self.label = label    def __le__(self, other):        return self.key <= other.key    def __repr__(self):        return f"{self.key}:{self.label}"def merge_sort(items):    source = list(items)    n = len(source)    if n <= 1:        return source    aux = [None] * n    _sort(source, aux, 0, n)    return sourcedef _sort(source, aux, lo, hi):    if hi - lo <= 1:        return    mid = lo + (hi - lo) // 2    _sort(source, aux, lo, mid)    _sort(source, aux, mid, hi)    _merge(source, aux, lo, mid, hi)def _merge(source, aux, lo, mid, hi):    for k in range(lo, hi):        aux[k] = source[k]    i = lo    j = mid    for k in range(lo, hi):        if i >= mid:            source[k] = aux[j]            j += 1        elif j >= hi:            source[k] = aux[i]            i += 1        elif aux[i] <= aux[j]:            source[k] = aux[i]            i += 1        else:            source[k] = aux[j]            j += 1def _labels(items):    return [item.label for item in items]if __name__ == "__main__":    original = [5, 2, 8, 1]    assert merge_sort(original) == [1, 2, 5, 8]    assert original == [5, 2, 8, 1]    assert merge_sort([]) == []    assert merge_sort([7]) == [7]    assert merge_sort([3, 1, 2]) == [1, 2, 3]    assert merge_sort([4, 4, 4]) == [4, 4, 4]    assert merge_sort(list(range(20, 0, -1))) == list(range(1, 21))    tied = [Keyed(1, "a"), Keyed(2, "b"), Keyed(1, "c")]    assert _labels(merge_sort(tied)) == ["a", "c", "b"]    print("ok")

Key takeaways

Sort a half-open range from lo up to but not including hi, and split it at lo + (hi - lo) // 2.

Copy the range into a buffer before writing merged items back, so unread values survive.

Take the left item when the keys are equal; contiguous halves then make the sort stable.

Test the empty list, one item, an odd length, duplicates, a reversed list, and labeled ties.

Level 3 · Advanced: Rounds, real sorts, and the comparison limit

The same merges can be arranged without a recursive call. Start with runs of width 1. A run is a sorted piece, and a single item is a sorted piece, so width 1 needs no work. Then merge neighboring runs into runs of width 2, then 4, then 8, doubling the width until it covers the list. This is bottom-up merge sort. Each pass walks the list once and places every item once. The width loop is the whole schedule of rounds. A power of two is a length reached by doubling from 1, such as 2, 4, or 8. For any other length, the last run in a pass is shorter: the end of a run is capped at the length of the list, and merging a run with an empty neighbor copies that run through unchanged.

Two practical changes keep the merge and shift the cost. First, if the last item of the left run is already less than or equal to the first item of the right run, the boundary is already in order and the copy can be skipped. On a fully sorted list every boundary is like that, so the merges drop away. What remains is a pass that inspects each boundary, and the work is proportional to the length of the list. A reversed list has no such boundary, so the worst case still merges every run. Second, very short runs are cheaper to order by insertion sort. Insertion sort slides each new item into its place among the items already ordered. A merge of those same short runs spends most of its effort copying them through a buffer. For long lists, CPython uses a minimum run of 32 to 64 items, chosen so the later merges stay balanced.

Those two changes are the core of Timsort, the algorithm behind Python's sorted and list.sort, and behind Java's sort for objects. Timsort searches for runs that already happen to be ordered, stretches a short run with insertion sort until it reaches the minimum length, and then merges runs with a stable merge. Data in real programs is often partly ordered: a log with a new tail, a table sorted by one column and then by another. Timsort spends work where the order is broken and spends little where a run is already sorted. The plain merge sort in the earlier sections is the teaching form of that idea. It always runs every round, which makes the cost easy to see. Timsort is the library sort to reach for when the data may already contain ordered runs.

Merge sort is also how software orders data that does not fit in memory. Read a chunk that does fit, sort that chunk, and write the sorted chunk out as a run. Repeat until the input is a sequence of runs. Then merge the runs. A heap is a structure that returns the smallest item it holds, and lets you replace that item, in time proportional to the logarithm of how many items it holds. The logarithm here is the number of times that count can be halved. Put the current front item of each run into a heap. The smallest front is the next output item. Read a new front from that same run and put it back into the heap. With k runs and n items, each item is taken from a heap of k fronts, so the merge costs time proportional to n times the number of times k can be halved. Database systems sort large tables this way. Most of each run stays on disk. Only the front of each run is in memory, which is the shelf picture with the piles in another room.

On a linked list the merge can avoid the buffer of items. A linked list stores each item in a node, and each node holds a link to the next node. Merging two sorted lists rewires those links: the smaller front node is attached to the growing result, and the walk continues from the node that followed it. The items stay in their nodes. Finding the middle, where the split goes, takes a walk from the start of the list, because a linked list reaches an item by following links from the front. The extra memory is the chain of calls, one frame for each halving. The C++ standard library asks a linked-list sort to be stable and to use about n log n comparisons, where n log n means the length times the number of times that length can be halved. Common implementations do that with merge sort.

The cost has a compact description called a recurrence: an equation for the work on a list of length n in terms of the work on smaller lists. Let T(n) be that work. Sorting n items sorts two halves and then merges, and the merge places n items, so T(n) = 2 T(n / 2) + c n for some constant c that covers the placements and the bookkeeping. T(1) is a constant, because a single item returns immediately. Unroll it. The top merge costs c n. The two merges under it cost c n / 2 each, which adds to c n. Each deeper row of merges also adds to c n. A length that is a power of two produces log base 2 of n rows, that is, exactly the number of times n can be halved. The total is c n times that number of rows. The master theorem is a ready-made result for recurrences of this shape, and it gives the same bound. Lengths that are not powers of two add only a row or two of shorter runs, which does not change how the total grows.

This growth is the natural cost of putting a list in order by comparisons. Any sort that decides order only by comparing two items can be drawn as a tree. Each comparison has two outcomes, so a tree of height h has at most 2 to the power h leaves, and each leaf is one possible ordering. A list of n distinct items can be ordered in n! ways, where n! means n times (n minus 1) times (n minus 2) and so on down to 1. The tree needs at least one leaf per ordering, so h is at least the base-2 logarithm of n!. A standard bound from Stirling's approximation says that logarithm is at least n times log base 2 of n, minus about 1.44 n. The n log n term dominates as n grows. Big-O notation names an upper growth rate once constant factors are set aside: O(n log n) means the work grows in proportion to the length times the number of times that length can be halved. Big-Omega is the matching lower growth rate: Omega(n log n) means the work grows at least that fast. Merge sort is O(n log n) in the worst case, and every comparison sort is Omega(n log n) in the worst case, so merge sort meets the limit. Counting sort and radix sort can grow more slowly only because they use the shape of the keys, such as digits or a small range of integers, and they require assumptions a comparison sort does not make.

Choose another method when its trade is the one you need. Insertion sort fits a few dozen items, where the buffer and the rounds are more bookkeeping than a short series of slides. Heapsort fits when a second copy of the list will not fit in memory: it rearranges the list using a constant amount of extra memory and still finishes in O(n log n) time in the worst case. Heapsort does not keep equal items in their original order. When the data is partly ordered and stability matters, call the run-aware merge the language already ships: Python's sorted, or Java's object sort. When you need the smallest k items and the order of the rest is irrelevant, a heap selection does that without producing a fully sorted list. Merge sort remains the method to study first, because the rounds, the stable merge, and the matching lower bound are all visible in it.

class Keyed:    def __init__(self, key, label):        self.key = key        self.label = label    def __le__(self, other):        return self.key <= other.keydef merge_sort(items):    source = list(items)    n = len(source)    aux = [None] * n    width = 1    while width < n:        for lo in range(0, n, width * 2):            mid = min(lo + width, n)            hi = min(lo + 2 * width, n)            merge(source, aux, lo, mid, hi)        width *= 2    return sourcedef merge(source, aux, lo, mid, hi):    for k in range(lo, hi):        aux[k] = source[k]    i = lo    j = mid    for k in range(lo, hi):        if i >= mid:            source[k] = aux[j]            j += 1        elif j >= hi:            source[k] = aux[i]            i += 1        elif aux[i] <= aux[j]:            source[k] = aux[i]            i += 1        else:            source[k] = aux[j]            j += 1if __name__ == "__main__":    assert merge_sort([]) == []    assert merge_sort([1]) == [1]    assert merge_sort([5, 2, 8, 1]) == [1, 2, 5, 8]    assert merge_sort([3, 1, 2]) == [1, 2, 3]    assert merge_sort([4, 4, 4]) == [4, 4, 4]    assert merge_sort(list(range(50, 0, -1))) == list(range(1, 51))    tied = [Keyed(1, "a"), Keyed(2, "b"), Keyed(1, "c"), Keyed(2, "d")]    assert [item.label for item in merge_sort(tied)] == ["a", "c", "b", "d"]    print("ok")

Key takeaways

Bottom-up merge sort merges runs of width 1, then 2, then 4, with no recursive calls.

Skipping an already ordered boundary, and insertion-sorting short runs, is the step from merge sort to Timsort.

Files that do not fit in memory are sorted as runs and then merged from a heap of their front items.

Every comparison sort needs Omega(n log n) comparisons in the worst case, and merge sort meets that bound.

Complexity

Time: O(n log n) best, average, and worst case

Space: O(n) extra space for the buffer, plus O(log n) stack frames in the top-down form

The plain algorithm always merges. A list of length n needs a number of rounds equal to the number of times n can be halved, rounded up, because each round doubles the sorted run width from 1 toward n. Each round places every item once, and each placement makes at most one comparison, so a round is O(n) work. The product is O(n log n) in the best, average, and worst case. Here O(n log n) means the work grows like the length times the number of halvings, ignoring constant factors. The buffer holds n items. The top-down calls add one waiting frame per round, which is O(log n) stack space and does not change the O(n) extra-space bound. The boundary-skip variant in the advanced section can bring an already sorted list down to O(n) time. That variant leaves the worst case at O(n log n).

Common mistakes

The range never shrinks. With inclusive ends, recursing on both sides of mid without dropping mid repeats the same range forever. Use a half-open range, from lo up to but not including hi, and recurse on lo, mid and on mid, hi, stopping when the width is under 2.

The leftover tail is dropped. When one half empties, the other half still holds sorted items that belong at the end. Copy that remainder before the merge returns.

The merge reads and writes the same slots. A write then destroys an item a later read still needs. Copy the range into a buffer first, and write the merged items into the original range.

Equal keys take from the right half. The keys still end up ordered, and two equal items swap their original order. Take from the left half when the comparison is equal.

The buffer is left out of the memory budget. The algorithm keeps a second stretch of storage proportional to the length of the list. When that buffer will not fit, use a sort whose extra memory is a constant amount.

The midpoint is computed by adding the two ends first, in a language with fixed-size integers. A large lo plus a large hi can overflow, and the midpoint becomes nonsense. Compute lo + (hi - lo) // 2.

Practice problems

Sort 4, 1, 3, 2 by hand (easy). Hint: Use the same shelf method as 5, 2, 8, 1. Write every pile after each split and after each merge.

Merge the sorted lists 1, 4, 9 and 2, 3, 9 (easy). Hint: Keep one index into each list and move the smaller front forward. Choose the tie rule before you start, because 9 appears in both lists.

Count inversions while merging (medium). Hint: An inversion is a pair that is out of sorted order. Watch the moment the next placed item comes from the right half, and ask which items still waiting on the left it has just jumped ahead of.

Skip a merge when two runs are already one run (medium). Hint: The decision can be made by looking at the boundary between the left run and the right run, before any copying starts.

Sort a linked list with merge sort (hard). Hint: The split point can be found by a walk from the first node, and the merge can rewire links instead of copying items into a buffer.

Argue the comparison lower bound (hard). Hint: Start from the number of possible orders of n distinct items, and from the fact that one comparison has two outcomes.

Summary

Merge sort is divide and conquer made visible on one list. Split 5, 2, 8, 1 until every piece is a single item, then merge those pieces by taking the smaller front and taking the left front on a tie, until the shelf reads 1, 2, 5, 8. The indexed version does that with one buffer, half-open ranges, and a midpoint of lo + (hi - lo) // 2, and the tests cover an empty list, one item, an odd length, duplicates, and labeled ties. Stability follows because each half is contiguous, each half is already stable, and equality prefers the left half. Bottom-up merge sort runs the same merges as explicit passes of doubling width. Timsort, external run merges, and linked-list sorts are that pattern with a shortcut for ordered boundaries, a heap of fronts, or links instead of a buffer. Every plain round places each item once, and the rounds are the number of times the length can be halved, so the time is O(n log n) in the best, average, and worst case, with O(n) extra space. That meets the Omega(n log n) limit on every sort that uses only comparisons, which is why this cost is the natural cost of putting things in order.