Merge sort and quick sort in Python

Why this lesson matters

The sorts in the last two lessons take O(n squared) time in the worst case. That is fine for ten numbers and painful for a million. The two sorts in this lesson take O(n log n) time, which is the best that any comparison sort can do in the worst case. Merge sort achieves it on every input. Quick sort achieves it on average, and many libraries use it for plain numbers.

Both sorts are also the standard examples of divide and conquer, a way of designing algorithms that you will use in many later modules. The idea is to split a big problem into smaller problems of the same kind, solve each small one, and then combine the answers. Once you can see that pattern, you can write recursive solutions to problems on trees, graphs and strings.

This lesson works through both sorts from first principles. You will write them, trace them, count their work, and learn the single weakness of quick sort that interviewers ask about most. Python also has a limit on recursion depth that Java does not have in the same form, and this lesson shows it.

Recursion in plain words

Both sorts use recursion, which means a function that calls itself. Recursion sounds strange until you see the rule that keeps it safe. A recursive function has two parts. The first part is a base case, a small input that the function answers directly without calling itself. The second part is the recursive case, which calls the same function on smaller inputs.

Here is an everyday picture. You want to find a name in a very large phone book, and you ask the people sitting in each row to check their own half. Each person does the same. Keep splitting until one person has one page, which is an easy base case. The answers come back up the rows and are combined.

In Python, each call to a function gets its own frame on the call stack. A frame holds the function's parameters and local variables. When a function calls itself, a new frame is pushed on top of the old one. When a call finishes, its frame is popped and the program continues in the frame below. The call stack has a limited size. Python sets a limit on how deep the calls may go, and the default limit is 1000. If recursion goes deeper than that, Python stops the program with a RecursionError. Keep that in mind, because quick sort has a version that goes very deep.

You can read the limit with sys.getrecursionlimit(). The limit exists to protect the computer from running out of memory for frames. Raising it with sys.setrecursionlimit() is possible, but it does not make a deep recursion safe, and this lesson shows a better fix.

The rule for every recursive function in this module is the same. Write the base case first, then make sure each recursive call works on a smaller range. Without the base case, the calls never stop.

Merge sort

Analogy. Picture a friend and you need to sort a big pile of exam papers by roll number. You split the pile in half and give one half to your friend. Each of you splits your half again, and again, until a pile has one paper. A pile of one paper is already sorted. Now merge two sorted piles. Compare the top paper of each pile, take the smaller one, and place it on your new pile. Repeat until both piles are empty. The result is one sorted pile.

The idea. Merge sort does exactly that with a list. The recursive function sorts the left half and the right half, then merges them. Splitting stops at size one, the base case. Merging two sorted halves is easy and takes one pass.

The function works on a range of the list. The range starts at lo and ends just before hi, so lo is included and hi is not. This is the same convention that Python's own range and slices use, so the sizes are easy to read: the range [lo, hi) has hi - lo values.

def merge_sort(a, lo, hi):              # sorts a[lo:hi], hi not included
    if hi - lo < 2:
        return                          # base case: zero or one value is sorted
    mid = lo + (hi - lo) // 2           # the middle, written with floor division
    merge_sort(a, lo, mid)              # sort the left half
    merge_sort(a, mid, hi)              # sort the right half
    merge(a, lo, mid, hi)               # combine the two sorted halves

The // operator is floor division. It divides and throws away the fraction, so 7 // 2 is 3. The formula lo + (hi - lo) // 2 is used instead of (lo + hi) // 2, which gives the same answer in Python. The reason it is written this way is explained in the common mistakes section.

The merge step takes two sorted runs that sit side by side and puts them into one sorted run. It needs a temporary list, because it cannot overwrite the input while it still needs it.

def merge(a, lo, mid, hi):
    tmp = []                             # room for the merged result
    i = lo                               # next unread value in the left run
    j = mid                              # next unread value in the right run
    while i < mid and j < hi:
        if a[i] <= a[j]:
            tmp.append(a[i])             # take from the left on a tie
            i += 1
        else:
            tmp.append(a[j])
            j += 1
    tmp.extend(a[i:mid])                 # one run is empty; add the rest of the other
    tmp.extend(a[j:hi])
    a[lo:hi] = tmp                       # copy the merged values back into place

The line a[lo:hi] = tmp is a slice assignment. It replaces the part of the list from lo up to hi with the values in tmp. Python does the copy in one step, which is shorter than a loop. The slice a[i:mid] makes a new list with the values from i up to mid, and extend adds all of them to tmp.

The <= on the comparison line is important. On a tie, the value from the left run is taken first. The left run holds the values that came earlier in the original list, so equal values keep their input order. That makes merge sort stable. If you change <= to <, a tie takes the right value first, and stability is lost.

Trace the merge step on two small runs, [27, 38, 43] on the left and [3, 9, 10, 82] on the right. Both runs are already sorted.

• Compare 27 and 3. 3 is smaller, so take 3 from the right. tmp is [3].
• Compare 27 and 9. Take 9. tmp is [3, 9].
• Compare 27 and 10. Take 10. tmp is [3, 9, 10].
• Compare 27 and 82. Take 27 from the left. tmp is [3, 9, 10, 27].
• Compare 38 and 82. Take 38. Then compare 43 and 82. Take 43.
• The left run is now empty, so add the rest of the right run. The 82 goes last.

The result is [3, 9, 10, 27, 38, 43, 82], which is what the slice assignment puts into the list.

Now the full recursion. Take [38, 27, 43, 3, 9, 82, 10], which has seven values, so lo is 0 and hi is 7.

• The first call splits at mid = 3. The left half is [38, 27, 43] and the right half is [3, 9, 82, 10].
• The left half splits at mid = 1. The piece [38] is one value and is already sorted. The piece [27, 43] splits again into [27] and [43], which merge to [27, 43]. Then [38] merges with [27, 43] to give [27, 38, 43].
• The right half splits at mid = 5. The piece [3, 9] merges to [3, 9]. The piece [82, 10] merges to [10, 82]. Then the two pieces merge to [3, 9, 10, 82].
• The top-level merge takes [27, 38, 43] and [3, 9, 10, 82], as traced above, and the final list is sorted.

Step through the sort below. Watch the pieces split, then merge back together.

The next program runs merge sort on the same seven values. It has the data built in, so you can run it without typing input.

The output is:

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

The output matches the trace. The program does not print the steps, so use the trace and the visualizer to see them.

Why merge sort is O(n log n)

Count the work in two parts. The splitting creates a tree of calls. Start with n values. Each level of the tree halves the size of every piece, so after about log n levels every piece has one value. For n equal to 8, that is 3 levels, because 2 to the power 3 is 8. For n equal to 1,000,000, it is about 20 levels, because 2 to the power 20 is about one million.

Each level of the tree merges all n values once. The merge walks the two runs, so the work at one level is proportional to the number of values on that level, which is n in total. Multiply n work per level by about log n levels and you get O(n log n). This count does not depend on the input order. Sorted input, reversed input and random input all split the same way and merge the same amount, so merge sort is O(n log n) in every case.

The price is memory. Each merge creates a tmp list, and the sort uses O(n) extra space at the top level. The recursion itself uses O(log n) frames at a time. The basic version uses O(n) extra space.

Using merge sort to count inversions

Merge sort is more than a sort. The merge step already compares values across the two runs, so it can answer questions about pairs. An inversion is a pair of values that are out of order. In the list [2, 4, 1, 3, 5], the pairs (2, 1), (4, 1) and (4, 3) are inversions, because the bigger value comes first. Counting inversions tells you how far a list is from sorted, which is useful for comparing rankings.

Brute force checks every pair, which is O(n squared). Merge sort can count them in O(n log n). The trick is in the merge. When the right value is taken before the left one, that right value is smaller than every value still waiting in the left run, and every one of those waiting values forms an inversion with it. The number of waiting left values is mid - i.

def count_inversions(a, lo, hi, tmp):
    if hi - lo < 2:
        return 0
    mid = lo + (hi - lo) // 2
    inv = count_inversions(a, lo, mid, tmp) + count_inversions(a, mid, hi, tmp)
    i = lo
    j = mid
    k = lo
    while i < mid and j < hi:
        if a[i] <= a[j]:
            tmp[k] = a[i]
            i += 1
        else:
            inv += mid - i              # a[j] is smaller than every value still waiting on the left
            tmp[k] = a[j]
            j += 1
        k += 1
    while i < mid:
        tmp[k] = a[i]
        i += 1
        k += 1
    while j < hi:
        tmp[k] = a[j]
        j += 1
        k += 1
    a[lo:hi] = tmp[lo:hi]
    return inv

This version writes into tmp by index, not with append, so the same tmp list can be reused by every call. The caller creates it once with [0] * len(a).

In Java this count needs a long, because a large count can overflow a 32-bit int. Python integers have no size limit, so the count is always exact. The same code is safe in Python for lists of any length you can fit in memory.

The next program counts inversions for two inputs. The data is built in.

The output is:

3
10

The first answer is 3, for the pairs (2, 1), (4, 1) and (4, 3). The second list is reversed, so every pair is out of order. For five values there are 5 times 4 divided by 2, which is 10 pairs. Those two answers are the extremes for their sizes. Sorted input gives 0, and reversed input gives the largest possible count.

The call list(data) makes a copy, so the function sorts the copy and the list data in the loop stays unchanged.

Quick sort

Analogy. Imagine seating a class by height in one pass. Ask one student to stand, the pivot. Ask everyone shorter to move to the left side of the room and everyone taller to the right side. The pivot is now in its final place in the line. Repeat the same process on the left side, then on the right side. Each round puts one student in their final position and shrinks the problem.

The idea. Quick sort picks a value called the pivot. It moves every smaller value to the left of the pivot and every bigger value to the right. This step is called partitioning. After partitioning, the pivot is in its final sorted position, because all the values before it are smaller and all the values after it are bigger. The function then sorts the left part and the right part the same way.

Unlike merge sort, quick sort does most of its work before the recursive calls, in the partition step. There is almost nothing to do when the two halves are combined, because they are already in the right places.

There are several ways to partition. This lesson uses the Lomuto scheme, which is the simplest one to read. It takes the last value in the range as the pivot and scans from left to right. A variable i marks the end of the "smaller than pivot" zone.

def quick_sort(a, lo, hi):              # sorts a[lo..hi], hi included
    if lo >= hi:
        return                          # base case: zero or one value
    p = partition(a, lo, hi)            # p is the pivot's final index
    quick_sort(a, lo, p - 1)            # sort the values left of the pivot
    quick_sort(a, p + 1, hi)            # sort the values right of the pivot
 
def partition(a, lo, hi):
    pivot = a[hi]                       # the last value is the pivot
    i = lo                              # boundary: a[lo..i) are smaller than pivot
    for j in range(lo, hi):
        if a[j] < pivot:
            a[i], a[j] = a[j], a[i]     # move the smaller value into the left zone
            i += 1
    a[i], a[hi] = a[hi], a[i]           # put the pivot at its final index i
    return i

This version uses the range with hi included, which differs from merge sort. Both conventions are fine. The rule is to pick one per function and write it in a comment, so the reader knows which index is the last one.

Trace partition on [3, 1, 2]. The pivot is the last value, 2.

• i = 0, j = 0. Is a[0] (3) smaller than 2? No. Nothing happens.
• j = 1. Is a[1] (1) smaller than 2? Yes. Swap a[0] and a[1]. The list is [1, 3, 2]. Increase i to 1.
• The loop ends at j = 2 because range(0, 2) stops before 2. The pivot is at index 2.
• Swap a[i] (index 1, value 3) with a[hi] (index 2, value 2). The list is [1, 2, 3].
• Return i = 1. The pivot 2 is at index 1, which is its final place.

The two recursive calls get the ranges [0, 0] and [2, 2]. Both are single values, so both return at once. The final list is [1, 2, 3].

Now the bigger trace. Partition [5, 1, 4, 2, 3] with pivot 3 at the end.

• j = 0, value 5. Not smaller than 3. Nothing happens.
• j = 1, value 1. Smaller. Swap a[0] and a[1]. The list is [1, 5, 4, 2, 3], and i becomes 1.
• j = 2, value 4. Not smaller. Nothing happens.
• j = 3, value 2. Smaller. Swap a[1] and a[3]. The list is [1, 2, 4, 5, 3], and i becomes 2.
• The loop ends. Swap a[2] (value 4) with a[4] (the pivot 3). The list is [1, 2, 3, 5, 4].
• Return 2. The pivot 3 is at index 2. Left of it are 1 and 2, which are smaller. Right of it are 5 and 4, which are bigger.

Step through quick sort below. Each pivot lands in its final place as the picture shrinks.

What one partition costs

A single partition on a range of size m does m minus 1 comparisons. The loop for j in range(lo, hi) visits every value except the pivot once, and each visit does one comparison and at most one swap. Nothing inside the loop depends on how many values are already in place, so the cost is always about m, whatever the order.

This is the key fact for the whole algorithm. The total work of quick sort is the sum of the partition costs over all the calls. If every partition splits its range in half, the calls form a balanced tree with log n levels, and each level has partitions whose sizes add up to n. The sum is n times log n. If instead every partition removes only one value, the tree is a long chain with n levels, and the sizes are n, then n minus 1, then n minus 2, and so on. Those sizes add up to about n squared divided by 2. The shape of the tree is the whole story, and the pivot choice is what decides the shape.

The random pivot

The pivot choice decides the speed. Suppose the pivot is always the largest value in the range. Then every value is smaller than the pivot, so the left side holds all the other values and the right side is empty. The work for one partition is about the size of the range, and the next call has one value fewer. The total is about n plus (n - 1) plus ... plus 1, which is n times (n + 1) divided by 2. That is O(n squared). A sorted list with the last value as pivot is exactly this case, because the last value is always the biggest.

The fix is to choose the pivot at random. A random pivot is very likely to land near the middle, so both sides are about half the size, and the recursion is about log n levels deep. The program below swaps a random index into the last position, then runs the same partition. Python's random.randint(lo, hi) returns a random whole number from lo to hi, and both ends are included.

The output is:

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

The output is the same whatever pivot the random generator picks, because every pivot leads to a correct sort. The random choice changes only the speed. The seed 7 is fixed in this program, so the pivots are the same on every run. Change the seed and the pivots change, and the sorted list still comes out the same. That is the correctness check.

Picture the calls as a tree. With a random pivot, each partition splits the range somewhere in the middle most of the time, so the tree is short and bushy, about log n levels deep. Each level does about n total work, so the sort does about n log n steps. With the last value as pivot on sorted data, each partition splits off just one value, so the tree is a single long branch with n levels. The same n work per partition now adds up over n levels, and the total grows with n squared.

Now the worst case in numbers. The next program uses a sorted list of values and the last value as the pivot. It counts the comparisons inside partition, so you can see the n squared behaviour directly. The list size is 900. The reason is the recursion limit, which the next paragraph explains.

The output is:

n = 900, comparisons = 404550

The number 404550 is 900 times 899 divided by 2. Each partition step with the last value as pivot compares every value in its range once, and each step removes only the pivot from the range. So the comparisons form the sum 899 + 898 + ... + 1, which is the formula above. For n equal to 900, that is about 400 thousand. For n equal to 9000, it would be about 40 million. Quick sort with a bad pivot is fast for small inputs and very slow for big sorted inputs.

The value 900 was chosen on purpose. The same program with n = 2000 does not print a count. It stops with a RecursionError:

RecursionError: maximum recursion depth exceeded

The crash happens because each call removes only the pivot. The recursion goes one call deeper for every value, so 2000 sorted values need about 2000 nested calls, and Python stops at its limit of 1000. Java stops this kind of program with a StackOverflowError, and Python stops it with a RecursionError. The message is the same idea in both languages: the call stack ran out of room.

Raising the limit with sys.setrecursionlimit(5000) lets this 2000-value case finish, and it still makes about two million comparisons. It does not fix the problem. The sort still does n squared work, and a list of 100,000 sorted values needs about 100,000 nested calls, and raising the limit that far is not a safe fix. The real fix is the random pivot, which the program above shows. It keeps the depth near log n. Run the same sorted input of 2000 values with the random pivot and the count is about 23,000 to 28,000 comparisons in our test runs, not two million, and no error is raised. The exact number depends on the pivots the generator picks.

Random pivots remove this worst case from typical inputs. An attacker can still build input that is slow for a known pivot rule, which is why libraries use random or carefully chosen pivots, and sometimes switch to a different sort when the recursion gets too deep.

Comparing merge sort and quick sort

Quick sort is usually faster on lists in memory, even though merge sort does about the same number of comparisons. The reason is memory access. The partition walks through the list in order, which keeps the processor's cache busy. Merge sort also walks in order, but it copies everything to tmp and back at every level, which costs time. This is an everyday tradeoff: the method with the best count is not always the fastest on real hardware. In Python the copying is cheap compared with the cost of each Python-level step, so the gap between the two is smaller than it would be in C.

Merge sort wins when stability matters or when the data is not in a list. A linked list is a chain of nodes, where each node holds a value and a pointer to the next node. Sorting one with merge sort needs no extra space for the copy, because the nodes can be relinked. Sorting a file that is too big for memory uses an external merge sort: sort chunks that fit in memory, write them to disk, then merge the sorted chunks.

Python's own sorted() is a merge-based sort called Timsort. It is stable, and it is fast on lists that are partly sorted. You will rarely write these sorts for production code. You write them to understand what sorted() does and what it costs.

What happens inside the machine

Each recursive call creates a frame. In merge sort, the frames are stacked about log n deep, and at each frame the merge creates a new tmp list. Python allocates tmp on the heap, which is the part of memory for objects, and Python frees it once the merge returns and no name refers to it. The copying at the end of each merge is what costs time in practice.

In quick sort, the partition works on the same list in place. The only extra memory is the frames of the recursion. With a random pivot, the expected depth is about log n, so the stack stays small. With a bad pivot, the depth can reach n, and each frame takes memory. Python protects the computer by stopping at the recursion limit. That is the reason the worst case also threatens the stack.

The random number generator inside the random module is a small piece of code that produces numbers that look random. It starts from a seed. Two runs with the same seed give the same pivots, which is useful for testing. Python's random.Random(7) creates a generator with its own seed, so the test does not change the global random numbers that other code may use.

Common mistakes and their messages

Mistake 1: a missing base case. Quick sort without if lo >= hi: return keeps calling itself on ranges that have no values left. The function never reaches a stop. This program runs the sort on [3, 1, 2] with the base case removed:

The output ends with this message, and the lines above it repeat the same call many times:

  File "nobase.py", line 3, in quick_sort
    quick_sort(a, lo, p - 1)
    ~~~~~~~~~~^^^^^^^^^^^^^^
  [Previous line repeated 995 more times]
  File "nobase.py", line 2, in quick_sort
    p = partition(a, lo, hi)
RecursionError: maximum recursion depth exceeded

Read the last line first. RecursionError means the calls went deeper than the limit. The lines above show the call that repeats, which is the recursive call on line 3. The fix is the base case on the first line of quick_sort. Without it, the function does not stop, and Python stops it instead.

Mistake 2: mixing the two range conventions. Merge sort uses hi excluded and quick sort uses hi included in this lesson. If you copy one call into the other function, the last value is either missed or read twice. Write the convention in a comment at the top of each function, as the code does.

Mistake 3: forgetting to copy the temporary list back. If the last line of merge is missing, the merged values stay in tmp, and the list a keeps its old order. The program prints an unsorted list and gives no error. The debugging section shows how to find this.

Mistake 4: the middle formula. Java programs can overflow when they compute (lo + hi) / 2 with 32-bit integers, because the sum may not fit. Python integers have no size limit, so (lo + hi) // 2 gives the right answer here. The lesson still uses lo + (hi - lo) // 2, because the same habit protects you when you port this code to Java, C or another language with fixed-size integers.

Mistake 5: using < in the merge comparison. Changing a[i] <= a[j] to a[i] < a[j] still sorts the numbers correctly. The change matters only when you sort records with keys. The debugging section and the stability program below show the bug with records.

Mistake 6: passing len(a) as the last index. This lesson's quick sort includes hi, so the first call must be quick_sort(a, 0, len(a) - 1). Writing quick_sort(a, 0, len(a)) makes partition read a[hi] one box past the end, and Python raises IndexError: list index out of range on a three-value list. Check which convention a function uses before you call it.

Debugging walkthrough

Here is a merge with one missing line. It is meant to sort [3, 1]. Read the code and predict the result before you read on.

def merge(a, lo, mid, hi):
    tmp = [0] * (hi - lo)
    i = lo
    j = mid
    k = 0
    while i < mid and j < hi:
        if a[i] <= a[j]:
            tmp[k] = a[i]; i += 1
        else:
            tmp[k] = a[j]; j += 1
        k += 1
    while i < mid:
        tmp[k] = a[i]; i += 1; k += 1
    while j < hi:
        tmp[k] = a[j]; j += 1; k += 1
    # missing: a[lo:hi] = tmp

Trace it. lo is 0, mid is 1 and hi is 2. The left run is [3] and the right run is [1]. The first loop compares 3 and 1. Since 3 <= 1 is false, the code takes 1 into tmp. The second loop copies the rest of the left run, which is 3. Now tmp holds [1, 3], which is sorted. But nothing copies tmp back into a. So a still reads [3, 1].

Run it with a print to see the bug:

The output is:

tmp: [1, 3]
a: [3, 1]

The program shows no error. The merge looks correct when you read only the loops. The method for finding this kind of bug is:

1. Pick the smallest input that shows the wrong answer. Here it is two values.
2. Print the list before and after each step of the failing function.
3. Find the step where the list stops changing when it should.
4. Look at the last lines of the function, because a missing copy is the usual cause.

The print of tmp next to a shows the bug in one line. The output shows tmp sorted and a unchanged.

Variations and edge cases

• Median-of-three pivot. Instead of a random index, take the first, middle and last values, and use their median as the pivot. It works well on sorted and nearly sorted data, and it costs three comparisons.
• Three-way partition. When many values are equal, the Lomuto partition puts all equal values on one side, which makes the sort slow. A three-way partition splits into smaller, equal and bigger parts.
• Bottom-up merge sort. Merge the pieces of size 1, then 2, then 4, and so on, without recursion. It removes the call stack, which is useful when the input is so large that the recursion limit becomes a problem.
• Empty and one-value lists. Both sorts return at once when the range has fewer than two values. Always test these two cases.
• All values equal. Merge sort is unaffected. Quick sort with the Lomuto partition is slow, because every value is equal to the pivot and none is smaller. This is the reason three-way partitioning exists.

Stability with records

Merge sort is stable when the merge uses <=. The next program sorts pairs of a name and a mark by the mark only, using a key function. It compares the result with Python's sorted(), which is also stable.

The output is:

[('b', 1), ('d', 1), ('a', 2), ('c', 2)]
[('b', 1), ('d', 1), ('a', 2), ('c', 2)]

Both results keep the input order inside each mark. b comes before d because b was first in the input among the marks of 1, and a comes before c for the same reason among the marks of 2. The function merge_sort in this program returns a new list and leaves the input unchanged, because it builds its results with slices. The in-place version earlier in the lesson changes the list it is given.

The lambda lambda p: p[1] is a small function that takes a pair and returns its second item. It is the key that both sorts use. Changing <= to < in the merge would break the match between the two outputs, and that is the test to run when you change the merge.

Interview questions

Question: Why is merge sort O(n log n) in every case? Answer: it splits the list into halves about log n times, and each level of merging touches every value once. Neither the input order nor the values change the split, so the bound holds for all inputs.

Question: What makes quick sort O(n squared) in the worst case? Answer: a pivot that is always the smallest or biggest value, which splits the range into one empty side and one side of size n minus 1. A random pivot makes this very unlikely.

Question: Why does Python have a recursion limit? Answer: each call uses memory for its frame, and an endless or very deep recursion would use up the memory and crash the program. Python stops the program with RecursionError at a set depth, which is 1000 by default. A good answer also says that raising the limit does not fix a bad algorithm, and that the fix is usually a better pivot or a loop-based version.

Question: How would you find the number of inversions in a list of a million values? Answer: count them with the merge step in O(n log n) time. A brute force check of every pair is O(n squared), which is too slow for a million values.

Real-world uses

The sort command on Linux uses external merge sort for large files. It sorts chunks that fit in memory, writes the sorted chunks to temporary files, and merges them. The same idea runs inside database engines when the data is larger than memory.

Java's Arrays.sort for primitive arrays uses a dual-pivot quick sort. For object arrays and lists it uses TimSort, which is a merge-based sort that is stable and fast on partly sorted data. Python's built-in sorted() and list.sort() also use TimSort.

Divide and conquer appears in fast multiplication, in the closest-pair problem for points, and in many tree algorithms. The pattern you learned here carries over.

Practice

Try each exercise in a file first. Check your answer after you have made an attempt.

1. Trace the first split of merge sort on [5, 1, 4, 2]. What are the two halves?

Show the answer

mid is 2, so the left half is [5, 1] and the right half is [4, 2]. Each half then splits into single values, and the merges put them back in order.

2. Merge [1, 4, 9] and [2, 3, 10] by hand. Write the comparisons and the output.

Show the answer

Compare 1 and 2, take 1. Compare 4 and 2, take 2. Compare 4 and 3, take 3. Compare 4 and 10, take 4. Compare 9 and 10, take 9. The left run is empty, so add 10. The result is [1, 2, 3, 4, 9, 10].

3. Partition [4, 2, 5, 1, 3] with the last value as the pivot. Write the list after each swap and the returned index.

Show the answer

Pivot 3. j = 0: 4 is not smaller. j = 1: 2 is smaller, swap indexes 0 and 1, giving [2, 4, 5, 1, 3], and i becomes 1. j = 2: 5 is not smaller. j = 3: 1 is smaller, swap indexes 1 and 3, giving [2, 1, 5, 4, 3], and i becomes 2. The final swap puts the pivot at index 2, giving [2, 1, 3, 4, 5]. The returned index is 2.

4. Explain why a sorted list with the last value as the pivot causes O(n squared) work, using the formula for the sum.

Show the answer

Each partition removes only the pivot, because the last value is the biggest and every other value is on the left. The partition scans n minus 1 values, then n minus 2, and so on. The sum is (n minus 1) plus (n minus 2) plus ... plus 1, which is n times (n minus 1) divided by 2. That is O(n squared).

5. Change the quick sort so it uses the middle value as the pivot instead of a random one. Run it on the sorted list 1 to 2000 and count the comparisons. Is the result still O(n squared)? Does it still hit the recursion limit?

Show the answer

Swap a[mid] with a[hi] before partitioning, where mid = lo + (hi - lo) // 2. For a sorted list the middle value is the true median of each range, so the sides are balanced. The comparisons grow like n log n, not n squared. The count is far smaller than two million, and the depth stays near log n, so the recursion limit is not reached.

6. Explain why merge sort is stable when the merge uses <=, but quick sort with the Lomuto partition is not stable.

Show the answer

In merge sort, a tie takes the left value first, and the left value came earlier in the input, so equal values keep their order. In the Lomuto partition, a smaller value far to the right can be swapped past several equal values, which changes their order.

7. Write a function count_pairs_with_sum_less(a, limit) that counts pairs i < j where a[i] + a[j] < limit, using sorting and two pointers. Explain the time complexity.

Show the answer

Sort first with sorted(), then use two pointers lo and hi. If a[lo] + a[hi] < limit, all pairs from lo up to hi - 1 with hi are valid, so add hi - lo and move lo up. Otherwise move hi down. The sort is O(n log n) and the scan is O(n), so the total is O(n log n).

8. Write a function merge_sort_copy(a) that returns a new sorted list and leaves the input unchanged.

Show the answer

def merge_sort_copy(a):
    copy = list(a)
    merge_sort(copy, 0, len(copy))
    return copy

The list(a) call makes a new list, so the caller's list is untouched. A shorter way is sorted(a), which does the same job.

9. Explain why Python does not need the form lo + (hi - lo) // 2 to avoid overflow, but a Java program does.

Show the answer

Java's int has a fixed size, about 2.1 billion at most. The sum lo + hi can be larger than that and wrap to a negative number. Python integers grow as large as needed, so (lo + hi) // 2 is always correct. The form lo + (hi - lo) // 2 is still a good habit for code that may be ported.

10. Explain why the pivot in quick sort can be any value in the range, but the partition must still end with the pivot in its final index.

Show the answer

Any pivot gives a correct sort, because the partition puts every smaller value left and every bigger value right. The final index of the pivot is where it belongs in the sorted list, so the two recursive calls can sort the sides independently. A pivot that is not placed at its final index would leave values on the wrong side of it.

What you now know

• Divide and conquer splits a problem into smaller copies, solves them, and combines the answers. Every recursive function needs a base case.
• Merge sort splits in halves and merges with a temporary list. It is O(n log n) in every case, and it is stable when the merge takes the left value on ties.
• Merge sort can count inversions by counting the right values that jump ahead of the left ones during the merge. Python integers do not overflow, so the count is always exact.
• Quick sort partitions around a pivot, which lands in its final place. It is O(n log n) on average and O(n squared) in the worst case.
• A random pivot makes the worst case very unlikely. A sorted list with the last value as pivot is the classic bad case.
• Python stops deep recursion with RecursionError at a limit of 1000 by default. Read the last line of a traceback first, then check the base case.