Merge sort in Python

Why it matters

Merge sort is a sorting method with a guaranteed speed. Whatever the input looks like, it takes about n log n steps, and that promise is what makes it valuable. It is also the clearest example of divide and conquer in this module: the work splits in half, the halves are solved, and the answers are joined by a merge step. The same merge step is reused in later problems, including counting inversions, which you will meet in the last lesson of this module.

Interviewers ask about merge sort for three reasons. They want to see you write the merge step without errors. They want you to explain why the running time is n log n in every case. And they want you to know the trade-offs against quick sort, which is the subject of the next lesson. This lesson covers all three.

You should already know lists, for loops, and recursion from the previous lesson. You also need the idea of a stack frame, which the last lesson explained.

The idea from first principles

Start with a question that looks too easy to matter: how do you combine two sorted piles of cards into one sorted pile?

Put the two piles face up on the table, each with its smallest card on top. Compare the two top cards. Take the smaller one and place it on a new pile. Now there is a new top card on the pile you took from. Compare again and take the smaller. Repeat until one pile is empty. Then put the rest of the other pile on the end, since it is already in order.

That is the merge step, and it has a striking property. Each card is looked at once. If the piles hold a total of n cards, the merge takes about n comparisons. You never go back to earlier cards. The sorted order of each pile is what makes this possible: the top card is always the smallest card left in its pile, so the smaller of the two tops is the smallest card left overall.

Now the divide and conquer idea. You cannot merge unsorted piles. But a pile with one card is already sorted. So split any pile in half, sort each half by the same method, and then merge the two sorted halves. The sorting of each half is just a smaller sorting problem of the same kind, so you call the same function on it. The recursion stops at piles of size one, which are the base case.

The three steps are:

1. Divide: split the list into a left half and a right half at the middle.
2. Conquer: sort each half by calling merge sort on it.
3. Combine: merge the two sorted halves into one sorted run. A run is a stretch of a list that is already in order.

Write it down as a rule you can check. A range of zero or one items needs no work. A bigger range is sorted by sorting its two halves and then merging them. Everything else follows from that rule.

The precise version in Python

Here is merge sort for a list of integers. The function sorts the range from index lo to index hi, both included. Read it once for the big picture, and then read the merge function, which does the real work.

The output is:

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

The function changes the list a in place, which means it does not return a new list. It returns None, and the caller sees the sorted values in a afterwards. Python's own list.sort() works the same way.

Look at the first lines of merge_sort. The base case is lo >= hi, which covers a range with zero items (when hi is one less than lo) and a range with one item (when they are equal). Both need no work. The middle is computed with the form you learned in the last lesson.

Now look at merge. The variables i and j are the read positions in the left and right halves. The list tmp collects the merged values in order. The method append adds one value to the end of a list, so tmp grows as the merge runs. The first while loop does the card-pile comparison: it copies the smaller front value and moves that side forward. The next two loops handle the leftovers. Exactly one half still has items when the first loop ends, and those items are already in order, so they are copied as they are. Finally the for loop with enumerate moves the merged run from tmp back into the original list, at the right position lo + k. The function enumerate gives each value together with its position, starting at 0.

Notice a[i] <= a[j] rather than <. On a tie, the left item goes first. That detail matters for stability, which you will study in its own section below.

The two halves are inclusive ranges. The left half is lo to mid, and the right half is mid + 1 to hi. Keep that in mind whenever you change an index. Python's slices work differently, as the common mistakes section explains. Most merge sort bugs come from confusing an inclusive end with an exclusive one.

Worked example 1: a full trace with the output

Watch the function work on a small list, using the trace version below. The print statements show each split and each merge, and the indentation shows how deep in the recursion each call is. The expression " " * depth builds a string of spaces, one pair for each level. Multiplying a string by a number repeats it in Python.

The output is:

split [5, 2, 4, 1]
  split [5, 2]
  merged [2, 5]
  split [4, 1]
  merged [1, 4]
merged [1, 2, 4, 5]
result [1, 2, 4, 5]

The line a[lo:hi + 1] is a slice. It copies the part of the list from index lo up to, but not including, index hi + 1. That is why the code adds 1 to get the inclusive end. The slice is only used here for printing.

Trace it by hand once. The first call sees the range 5 2 4 1, which has four items, and prints it. It splits at the middle into 5 2 and 4 1. The call on 5 2 splits again into 5 and 2. Each of those is a single item, so both calls return at once. Then the merge of 5 and 2 runs. The first item from the left is 5, the first item from the right is 2. Since 5 is bigger, the function takes 2 first, then the left 5 is copied as a leftover. The result is 2 5, which the trace prints as merged [2, 5].

The call on 4 1 does the same thing. It merges to 1 4. Finally the top call merges 2 5 with 1 4. The first items are 2 and 1, so 1 goes first. Then 2 goes. Then 4 goes, and then 5 goes as a leftover of the left half. The result is 1 2 4 5.

The tree below shows the same work. The top line is the whole list, the middle lines are the splits, and the last line is the final merge.

[5, 2, 4, 1]
  [5, 2]  ->  [2, 5]
    [5]
    [2]
  [4, 1]  ->  [1, 4]
    [4]
    [1]
  merge [2, 5] and [1, 4]  ->  [1, 2, 4, 5]

Now step through the same kind of run with the visualizer. It shows the list splitting and the merged runs growing.

Watch two things. The first is that the splits happen before any comparison: the function breaks the work into small pieces first, and only then compares. The second is that each merge works on two runs that are already sorted, so it never has to search for the smallest item. It only compares the two front items.

Checking a merge with a table

When a merge goes wrong, a table is the fastest way to find the bug. Make one row for each comparison. Write the front value of each half, which value is taken, and what the tmp list holds afterwards. Here is the merge of 2 5 and 1 4 from the first worked example.

Each row takes the smaller of the two fronts, which is the rule in the comparison. Row 4 shows the leftover loop at work: the right half is empty, so the remaining left item is copied. If your own table differs from this one, the first row that differs shows you where to look. The table also shows why the result is always sorted. Each row takes the smallest value that remains in either half, so tmp grows in order from start to finish.

Worked example 2: merging two sorted lists

Look at this input: [1, 4, 9] and [2, 3, 10, 11]. Two sorted lists are merged by a function that does not sort. This is the combine step in isolation. The program prints the inputs, the merged result, a case where one list is empty, and a version without the leftover step, which is a bug you will meet soon.

The output is:

first:  [1, 4, 9]
second: [2, 3, 10, 11]
merged: [1, 2, 3, 4, 9, 10, 11]
empty:  [7, 8]
without leftovers: [1, 2, 3]

Trace the merge of the first two lists. The fronts are 1 and 2, so 1 goes out. The fronts are 4 and 2, so 2 goes out. The fronts are 4 and 3, so 3 goes out. The fronts are 4 and 10, so 4 goes out. Now the left list has 9 at its front and the right list has 10. The function takes 9. The left list is empty, so the first loop stops. The leftover step copies 10, 11. The output has seven items, which is 3 plus 4.

The function uses out.extend(left[i:]) for the leftovers. The slice left[i:] means "from index i to the end of the list." This does the same job as the two leftover loops in the earlier version. Either style is correct, and the slice is shorter.

The last line tests the case where the left list is empty. Without the leftover step, the first loop never runs, and the other list is lost. The version called merge_two_without_leftovers returns [1, 2, 3] for [1, 4] and [2, 3]. The 4 is missing because it was the last item of the left list, and nothing copied it. That is why the leftover step must be there even when it looks unnecessary.

Worked example 3: stability, shown with real data

A sort is stable when items with equal keys keep the order they had before sorting. Stability matters a lot in real programs. Imagine a list of students sorted by grade, where two students both have grade A. A stable sort keeps the two A students in the order they were entered. An unstable sort may swap them, and a user who sorted by name and then by grade could lose the first ordering.

The next program stores each student as a tuple, which is a fixed group of values written in parentheses. Each tuple holds the grade first and an id second. It sorts by grade only. Look at the ids in the output for the tied grades.

The output is:

grade 1 id 2
grade 1 id 4
grade 2 id 1
grade 2 id 3
grade 3 id 5
sorted() gives the same order: True

Look at grade 1. The input order had id 2 before id 4, and it still does. Look at grade 2. Id 1 came before id 3 in the input, and it still does. Stability comes from one character in merge: the <= in the comparison. On a tie, the item from the left half is taken first. The left half holds the items that came earlier in the original list, because the split keeps the original order within each half. So ties always keep their original order.

The last line uses Python's built-in sorted function with a key. The key is a function that picks the value to compare, here row[0], which is the grade. The lambda is a short unnamed function, and it is written lambda row: row[0]. Python's built-in sort is also stable, so the two results match. You can rely on that guarantee in your own code.

If you change <= to <, the program still prints grades in the right order, but the ids inside each grade can swap. That is a silent bug. It would only show up when someone checks the ids. This is exactly why stability should be a deliberate choice, and why you should test it with duplicate keys.

Sorting numbers that you type

A sorting program is more useful when it reads its own data. The next program reads a count and then that many numbers from standard input, sorts them with merge sort, and prints them on one line with single spaces between them. It uses the same merge_sort and merge functions as before, so you can focus on the reading and printing parts.

import sys
 
 
def merge_sort(a: list[int], lo: int, hi: int) -> None:
    if lo >= hi:
        return
    mid = lo + (hi - lo) // 2
    merge_sort(a, lo, mid)
    merge_sort(a, mid + 1, hi)
    merge(a, lo, mid, hi)
 
 
def merge(a: list[int], lo: int, mid: int, hi: int) -> None:
    tmp: list[int] = []
    i = lo
    j = mid + 1
    while i <= mid and j <= hi:
        if a[i] <= a[j]:
            tmp.append(a[i])
            i += 1
        else:
            tmp.append(a[j])
            j += 1
    while i <= mid:
        tmp.append(a[i])
        i += 1
    while j <= hi:
        tmp.append(a[j])
        j += 1
    for k, value in enumerate(tmp):
        a[lo + k] = value
 
 
def main() -> None:
    data = sys.stdin.read().split()
    n = int(data[0])
    a = [int(x) for x in data[1 : 1 + n]]
    merge_sort(a, 0, n - 1)
    print(" ".join(str(x) for x in a))
 
 
if __name__ == "__main__":
    main()

Save the file as sort_input.py. Then run this command:

printf '7\n38 27 43 3 9 82 10\n' | python3 sort_input.py

The output is:

3 9 10 27 38 43 82

The call merge_sort(a, 0, n - 1) works even when n is 0. Then hi is -1, which is less than lo, so the base case returns at once. The program prints an empty line. You do not need a separate check for an empty input.

A bottom-up version without recursion

The recursive version splits the list from the top down. You can also build the sort from the bottom up. Treat every single item as a sorted run of length one. Merge neighboring runs in pairs to make runs of length two. Then merge neighboring pairs of those to make runs of length four, and keep doubling until one run covers the whole list. This is a bottom-up merge sort. It uses loops instead of recursion. For lengths that are not a power of 2, it merges different runs than the recursive version does.

The variable width holds the length of the runs that are about to be merged. It starts at 1 and doubles after each pass. Inside a pass, lo jumps forward by two runs at a time. The left run is the width items starting at lo, and the right run is the next width items. Near the end of the list the right run can be shorter, which is why hi takes the smaller of two values with min. The loop range(0, n - width, 2 * width) gives the start of each left run, and it skips a last lonely run that has nothing to merge with.

The next program uses the same merge function as before and replaces the recursion with two loops.

The output is:

[3, 9, 10, 27, 38, 43, 82]
[1, 2, 3, 4, 5, 6]

Trace the first list to see the passes. In the first pass, with runs of length one, the pairs 38 27, 43 3 and 9 82 are merged, and the single 10 is left alone. The list becomes 27 38 3 43 9 82 10. In the second pass, runs of length two merge: 27 38 with 3 43 gives 3 27 38 43, and 9 82 with 10 gives 9 10 82. The list is now 3 27 38 43 9 10 82. In the third pass, the two runs of length four merge into one sorted run of seven items. The next width is 8, which is not less than 7, so the outer loop stops.

Bottom-up merge sort has the same O(n log n) time and O(n) extra space as the recursive version. It uses no recursion, so it cannot reach Python's recursion limit, although merge sort never needed deep recursion in the first place. Its loop bounds are harder to read, so choose whichever version your team finds clearer. Know both, because interviewers sometimes ask for the iterative form.

Counting comparisons

Interviewers sometimes ask how many comparisons merge sort makes, not only how many steps it takes. The answer depends on how the two runs interleave. The program below counts the comparisons in one merge.

The output is:

[1, 2] and [3, 4]: ([1, 2, 3, 4], 2)
[1, 3] and [2, 4]: ([1, 2, 3, 4], 3)
[1, 2, 3] and [4, 5, 6]: ([1, 2, 3, 4, 5, 6], 3)

Take two runs of length m each. If every item of the left run is smaller than every item of the right run, the merge takes m comparisons: the left run empties first, and the right run is copied without more checks. That is the best case for one merge. The first example, [1, 2] and [3, 4], shows this with m equal to 2. If the runs alternate, such as [1, 3] and [2, 4], the merge takes 2m minus 1 comparisons, which is 3 when m is 2. The second example shows this. The third example has m equal to 3 and takes 3 comparisons, because the left run empties first again.

Across the whole sort, the best case adds up to about n divided by 2, times log base 2 of n, and the worst case is about n times log base 2 of n. Both are O(n log n). The gap is only a constant factor, and the big-O bound does not change. This is why the proof in the next section counts work per level rather than comparisons. Counting comparisons is a useful exercise, but you do not need the exact number to explain the running time.

Time: why it is always n log n

Now prove the running time, because interviewers ask for proof, not just the answer.

Look at the recursion as a tree. The top call works on n items. It makes two calls, each on about n / 2 items. Each of those makes two calls on about n / 4 items. The tree keeps splitting until each piece holds one item. Each split halves the size, so the number of levels is about log base 2 of n. The rule from the first lesson gives the same count.

Now count the work at each level. A merge at any level reads every item in its range once and writes it once. The ranges at one level cover the whole list with no overlap, so one level costs about n steps in total. Across about log n levels, the total is n times log n. Mathematicians write this as O(n log n).

The most important part of this proof is that nothing in it depends on the input order. The list can be sorted, reversed, or random, and the tree has the same shape. Each level still does n work, and the number of levels does not change. That is why merge sort is n log n in the best case, the average case and the worst case. A method whose work never depends on the data is predictable, and predictability is valuable in production systems with deadlines.

Compare this with the counting of loop steps in binary search. Binary search does one small job per level and throws most of the data away. Merge sort does a full pass over the data at every level and keeps everything. That difference explains why sorting costs more than searching.

Space: the cost of merge sort

Merge sort has one real cost, which is memory. The merge function creates the temporary list tmp each time it runs. At the top level, tmp holds n items. The call stack adds about log n frames, which is small. Overall, merge sort uses O(n) extra space, plus O(log n) for the stack.

You can reduce the cost in practice. Allocating one shared tmp list of size n, passed into every call, avoids creating a new list for each merge. That does not change the big-O cost, since the buffer still has size n, but it removes thousands of allocations on large inputs. The practice answers at the end of this lesson show how to write it.

The space cost is the main reason some systems choose a different sort. An in-place sort such as quick sort uses almost no extra memory. You will see that trade-off in the next lesson.

What happens inside: the memory of a merge

Picture the list as a row of slots, each holding a reference to a value. The merge reads from two places in that row, i and j, and writes to a second list, tmp. Then it copies tmp back. The copy-back is important: it means the list holds the merged result in the correct positions before the caller moves on.

Here is a trace of the memory during one merge of [2, 5] and [1, 4], which is the top-level merge in the earlier trace.

index:   0  1  2  3
list:    2  5  1  4    before: left run 2 5, right run 1 4
tmp:     1  2  4  5    merged in order, built with append
list:    1  2  4  5    copied back into positions 0 to 3

Each value is read once from the list and written once to tmp. The copy back touches each position once more. So the merge makes about 3n memory operations for n items, which is still O(n).

Common mistakes and the errors they cause

Merge sort is short, but it has several traps. Learn to spot them.

Mistake 1: the temporary list is too short. If you create the buffer with [0] * (hi - lo) and write into it by position, instead of creating the list empty and using append, the buffer is one item too short. The last value written goes past the end, and Python reports:

IndexError: list assignment index out of range

The message says the program tried to assign to a position that does not exist in the list. The fix is to make the buffer hold hi - lo + 1 items, which is the number of items in the range. Count the items in a small example to check. The append style in this lesson avoids the problem because the list grows as needed.

Mistake 2: copying back to the wrong position. The copy-back must write to a[lo + k], not a[k]. Writing to a[k] works for the first merge at the very start of the list, which is why the bug is easy to miss. It fails for any merge that starts later in the list. Python gives no error. Sorting indexes 2 to 5 of a six-item list with the copy-back line changed to a[k] = value gives this:

input:   [9, 8, 5, 1, 4, 3]
output:  [4, 3, 5, 1, 4, 3]

The values 9 and 8 are gone, and the values 4 and 3 each appear twice. Nothing was reported, and the list looks like data. Test with an input whose range starts past index 0, such as sorting only the right half of a list.

Mistake 3: forgetting the leftover steps. If you drop the two loops or the extend calls for leftovers, the last items of one half are lost. You will see a short output with missing numbers. The example in worked example 2 shows this exactly. Make sure the leftover steps come after the main loop.

Mistake 4: using < instead of <=. The output is still sorted, so the bug only shows when you check stability with duplicate keys. Keep the <= on purpose and write a test for it.

Mistake 5: the wrong inclusive or exclusive end. Python slices stop before the end index. The slice a[1:3] gives the items at indexes 1 and 2, not 3. The program below shows this with a list of four values.

The output is:

[20, 30]
[20, 30, 40]

Because the merge uses inclusive ends, a slice must end at hi + 1 to include index hi. If you write a[mid:hi] by mistake, the last item is dropped. If you write the right half as mid to hi, it overlaps the left half, and values get copied twice. Use mid + 1 for the start of the right half, and keep your ranges inclusive throughout.

Mistake 6: comparing values of different types. Python compares values with <=, and it refuses to compare a text value with a number. If a list holds 3, "1" and 2, the merge stops with an error:

TypeError: '<=' not supported between instances of 'int' and 'str'

The message names both types. The fix is to make all the values the same type before you sort, for example by converting the text with int().

Debugging walkthrough: a merge that loses items

Here is a bug that is easy to create. A teammate deleted the loop that copies the leftover items of the left half. Test it on [1, 4] and [2, 3], as worked example 2 did. The result is [1, 2, 3], with the 4 missing. The output has the wrong length, which is the first clue. Do not start by reading the whole program. Ask which values went missing. The 4 was the last item of the left half, and the leftover step for the left half is the only code that could have added it. The fix is to put back the loop while i <= mid: with its append, or the out.extend(left[i:]) line.

Use this habit whenever a sort gives a wrong answer. Count the items in the output and compare them with the input. If the count is wrong, the bug is in the copy logic. If the count is right but the order is wrong, the bug is in the comparison or in the copy-back index. Check the length first. It takes seconds and narrows the search a lot.

For a stronger check, test the sort against a trusted answer. The next program does exactly that. It generates 200 random lists, sorts each with merge sort, and compares the result with Python's built-in sorted. The random number generator is seeded, so every run uses the same lists and the output never changes.

The output is:

all 200 trials passed

The test covers empty lists, single items, duplicates (there are only 100 possible values, so repeats are common), and negative numbers. That is a much better check than a single example, because bugs often hide at the edges. The random.Random(7) object is a separate generator with a fixed seed, so the same numbers come out on every run. Without a fixed seed, a test that fails once might pass on the next run and hide the bug.

Variations and where merge sort is the right tool

Merge sort has several strong uses that you should know by name.

Sorting a linked list. A linked list has no index, so you cannot jump to the middle in one step. Merge sort still works, because it only needs to split the list in half and then merge two sorted lists. Merging needs only the front of each list, not random access to any position. Quick sort, which depends on swapping by index, is much harder on a linked list. That is one reason merge sort is a favorite for linked list questions.

Sorting data too big for memory. When the data is in a file, you can sort chunks that fit in memory, write each sorted chunk to a file, and then merge the files. The merge step reads only the front of each file. This is called an external sort, and it is how large databases sort big tables.

Merging k sorted lists. A common interview question gives you k sorted lists and asks for one sorted list. Python's standard library has heapq.merge for this. The program below merges three lists.

The output is:

[1, 2, 3, 4, 5, 6, 7]

The function heapq.merge reads the front of each list and returns the smallest, one value at a time, so it works on very long inputs. It is a lazy generator, which means it produces values as you ask for them. The list(...) call collects them into a list. You can also merge the lists in pairs, the same way merge sort does, which takes O(n log k) time. A heap, which you will meet later in the course, is the tool that makes the choice of smallest value fast.

Python's built-in sort. sorted() and the method list.sort() are built into Python. They use a method called Timsort, which is stable and works on any values that can be compared. For most code, you should call these instead of writing your own sort.

Why not just call sorted?

In real code you usually call a built-in sort, and you should. sorted and list.sort are tested, fast, and maintained by people who work on them full time. So why learn to write merge sort? There are three reasons. First, interviews ask you to write it. Second, the merge step is a building block for other problems, such as counting inversions and merging sorted files, and those need the merge itself, not the whole sort. Third, you sometimes need a sort the library does not offer, such as one with a custom merge rule or one that works on data arriving in pieces.

One detail matters in practice. sorted returns a new list and leaves the original alone. list.sort() changes the list in place and returns None. Both are stable, so the input order of equal keys is kept. The merge sort in this lesson also changes its list in place, which is why the trace shows the list after each step.

Interview questions you should be ready for

• "Why is merge sort O(n log n) even in the worst case?" Explain the level count and the n work per level, and say that the work does not depend on the input order.
• "Is merge sort stable? Show me where." Point to the <= in the merge comparison, and explain why ties take the left item first.
• "What is the extra space?" O(n) for the temporary list, plus O(log n) for the call stack. Mention the shared buffer as a practical improvement.
• "Sort a linked list." Explain the split-and-merge version. Mention that it needs no random access.
• "Count the inversions." Explain that the merge step can count them, which the last lesson of this module covers in detail.

Practice

Try each exercise on your own before you open the solution. The hints are short on purpose.

1. Trace merge sort on [5, 2, 4, 1] and write down the order of the splits and merges. Hint: the last merge combines [2, 5] and [1, 4].

2. Change the program so it sorts in descending order, from largest to smallest. Hint: flip one comparison in merge, and keep the leftover steps.

3. Explain why merge sort is a good choice for a linked list, using the phrase "random access" in your answer. Hint: merging reads only the fronts of two lists.

4. Write a function that returns the number of levels of splitting for a list of length n, without running the sort. Hint: keep halving the length until it is 1, counting the halvings. For 8 items the answer is 3.

5. Change merge so it uses only one shared buffer for the whole sort, created once in the main program. Hint: pass the buffer into every call and index it with k starting at lo, then copy back the same range.

6. A teammate says that merge sort on the already sorted list [1, 2, 3, 4] does fewer comparisons than on a random list. Is that true for the merge in this lesson? Hint: count the comparisons in one merge of [1, 2] and [3, 4].

7. Write a function that returns True if a list is sorted from smallest to largest. Hint: compare each item with the one after it.

8. Write a function that merges two sorted lists of different sizes and returns the result. This is the combine step on its own. Hint: the function merge_two in worked example 2 already does this.

9. Given the rows (2, 7), (1, 8), (2, 9), (1, 10), sort them by the first number with a stable sort. Write the ids in the final order. Hint: the ids within each grade keep their input order.

10. Why does the test in this lesson use random lists with a fixed seed? Hint: think about what happens when a test fails and you want to run it again.

Show the answer

1. Split into [5, 2] and [4, 1]. Split [5, 2] into [5] and [2], and merge them into [2, 5]. Split [4, 1] into [4] and [1], and merge them into [1, 4]. Merge [2, 5] with [1, 4] into [1, 2, 4, 5]. There are three merges, and the splits go down two levels below the top.

Show the answer

2. In merge, change a[i] <= a[j] to a[i] >= a[j]. The leftover steps stay the same. On a tie the left item still goes first, so equal items keep their input order.

Show the answer

3. A linked list has no index, so you cannot read the middle or any item by position in one step. Merge sort only needs to split the list in half, which can be done with two pointers, and merge two lists by reading the front of each. Neither step needs random access, which means jumping straight to a position.

Show the answer

4. Start with a counter at 0. While n is greater than 1, set n to (n + 1) // 2, which is half rounded up, and add 1 to the counter. For 8 items the sizes are 8, 4, 2, 1, which is 3 halvings.

Show the answer

5. Create buf = [0] * len(a) in the main program and pass it to merge_sort and merge. In merge, start k at lo instead of 0, so each write goes to the same position as the range. After the merge, copy the range back with for k in range(lo, hi + 1): a[k] = buf[k]. The code below is one tested version.

def merge_shared(a: list[int], buf: list[int], lo: int, mid: int, hi: int) -> None:
    i = lo
    j = mid + 1
    k = lo
    while i <= mid and j <= hi:
        if a[i] <= a[j]:
            buf[k] = a[i]
            i += 1
        else:
            buf[k] = a[j]
            j += 1
        k += 1
    while i <= mid:
        buf[k] = a[i]
        i += 1
        k += 1
    while j <= hi:
        buf[k] = a[j]
        j += 1
        k += 1
    for k in range(lo, hi + 1):
        a[k] = buf[k]

The sort that calls it has the same shape as merge_sort, with buf passed down to each call. The main program creates the buffer once with buf = [0] * len(x).

Show the answer

6. In one merge of [1, 2] and [3, 4], the function compares 1 with 3, then 2 with 3, and then copies the rest of the right list. That is 2 comparisons. The same four numbers in another order, such as [1, 3] and [2, 4], need 3 comparisons. So the sorted input does fewer comparisons in the merge step. The total work is still about n log n, because every level still copies every item, and that copying does not depend on the order.

Show the answer

7. Use all with a loop over the positions before the last one. The check a[i] <= a[i + 1] must hold for every i. An empty list or a one-item list is sorted.

def is_sorted(a: list[int]) -> bool:
    return all(a[i] <= a[i + 1] for i in range(len(a) - 1))

Show the answer

8. Use the merge_two function from worked example 2. It already handles lists of different lengths, because each loop checks its own bound, and the leftover steps copy whatever remains.

Show the answer

9. The rows are (2, 7), (1, 8), (2, 9) and (1, 10), where the first number is the grade and the second is the id. The grade 1 rows are (1, 8) and (1, 10), in that input order, so their ids come first in the order 8, 10. The grade 2 rows are (2, 7) and (2, 9), so their ids follow in the order 7, 9. The final id order is 8, 10, 7, 9. Running sorted(rows, key=lambda r: r[0]) gives [(1, 8), (1, 10), (2, 7), (2, 9)], which matches.

Show the answer

10. A fixed seed means the random numbers are the same on every run. If a test fails, you can run it again and get the same failing list, which makes the bug reproducible. A test with no seed might pass on your next run and hide the bug.

What you now know

• Merge sort splits a list in half, sorts each half by calling itself, and merges the two sorted halves.
• The merge step compares the front items of two sorted runs and takes the smaller, so it needs one pass over the data.
• The method always takes O(n log n) time, because there are about log n levels and each level does about n work.
• It uses O(n) extra memory for the temporary list, plus O(log n) stack space.
• The comparison <= in the merge makes the sort stable, so equal keys keep their input order.
• Test the copy-back index, the buffer size, and the leftover steps. Check the output length first when a sort gives a wrong answer.
• Merge sort is a good choice for linked lists, external sorting and merging sorted lists. For everyday code, Python's built-in sorted is the right tool.