Divide and conquer
The recursive functions so far made their input smaller by one step in each call: one digit fewer, one disk fewer, one more number decided. In divide and conquer a call cuts its input into parts, usually two halves, and calls itself on each part. The standard example is sorting.
Given an array of integers nums, return it sorted in ascending order. Do not use a built-in sort function. The solution must run in time and use as little extra space as possible.
Constraints
-
nums.length -
nums[i]
Sample 1 · Input
nums = [5,2,3,1]
Output
[1,2,3,5]
Sample 2 · Input
nums = [5,1,1,2,0,0]
Output
[0,0,1,1,2,5]
A simple way to sort is selection sort: find the smallest value and put it first, then do the same with the rest. Finding the smallest of values takes comparisons, the next round takes , and so on. For the 50,000 values this problem allows, that is
about 12 seconds at roughly simple operations a second.
Selection sort is slow because a round makes the problem only one value smaller, so it takes rounds, and a round reads most of the list. Merge sort makes the problem smaller much faster, by halving it:
- A list of one value, or of none, is already sorted. Return it.
- Split the list at its middle into a left half and a right half.
- Sort the left half with a recursive call.
- Sort the right half with a recursive call.
- Merge the two sorted halves into one sorted list.
For example, take these eight values:
Step 2 splits them into two halves of four:
Steps 3 and 4 sort each half. As with every recursive function, we do not follow these calls down, and take it that they return their halves sorted:
Step 5 merges the two sorted halves into the answer:
This plan is called divide and conquer. It divides the input into smaller parts, each of which is the same problem on less input. It solves each part with a recursive call, and it combines their answers into the answer for the whole input. A part small enough to answer directly, like a list of one value, is the base case. In merge sort the divide step only cuts the list at its middle, and the recursive calls sort the halves, so all the real work is in the combine step, the merge.
Merge two sorted halves
Both halves are sorted, so the smallest value of all is at the front of one of them. To merge, we compare the two front values, move the smaller one to the output, and repeat with what is left.
| Left front | Right front | Moved to the output | Output so far |
|---|---|---|---|
| 3 | 5 | 3 | 3 |
| 27 | 5 | 5 | 3 5 |
| 27 | 9 | 9 | 3 5 9 |
| 27 | 10 | 10 | 3 5 9 10 |
| 27 | 82 | 27 | 3 5 9 10 27 |
| 38 | 82 | 38 | 3 5 9 10 27 38 |
| 43 | 82 | 43 | 3 5 9 10 27 38 43 |
| none left | 82 | 82 | 3 5 9 10 27 38 43 82 |
After seven comparisons the left half is empty, and the rest of the right half, here only the 82, is moved over without any more comparisons.
The output is sorted because each value moved is the smallest one remaining: it is the smaller of the two fronts, and each front is the smallest value left in its half. Merging values takes at most comparisons, since every comparison moves one value to the output and the last value needs none.
Merge sort in code
def merge_sort(a):
if len(a) <= 1:
return a
mid = len(a) // 2
left = merge_sort(a[:mid])
right = merge_sort(a[mid:])
out = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
out.append(left[i])
i += 1
else:
out.append(right[j])
j += 1
out.extend(left[i:])
out.extend(right[j:])
return out
print(merge_sort([38, 27, 43, 3, 9, 82, 10, 5]))
print(merge_sort([5, 1, 1, 2, 0, 0]))The if and its return are step 1, and the slices a[:mid] and a[mid:] are the two halves of step 2. The while loop is the merge shown in the table: i and j are the positions of the two fronts. The two extend lines after it move over whatever is left in the half that did not run out.
The comparison is <= so that when the two fronts are equal, the one from the left half is moved first. Equal values then come out in the order they went in, and a sort with this property is called stable. Stability matters when you sort records by one field: sort students by name, then stably by grade, and the students with the same grade stay in name order.
The call tree of merge sort on the eight values
The widget draws the call tree of merge sort on the same eight values. Each box shows the list a call receives and, once the call has returned, the sorted list it gives back.
Count the work of merge sort by level
The calls of merge sort do different amounts of work, a large merge at the top of the call tree and small ones further down. So instead of multiplying the number of calls by the work of one call, as we did for the Tower of Hanoi, we add the work up one level of the tree at a time. The top call merges all 8 values. The two calls below it merge 4 values each, 8 in total, and the four calls below those merge 2 each, again 8. The lists of one value on the last level need no merging.
In general every level moves each of the values once. The lists halve from one level to the next, so the number of levels that merge is the number of times can be halved before it reaches 1, which is , rounded up. That gives about moves and no more comparisons than moves, so merge sort runs in time.
For 50,000 values there are 16 such levels, since is below 50,000 and is above it. That is at most
about 1,560 times fewer than the comparisons of selection sort.
The split does not have to be exactly in half. If every call put a third of its list in one part and the other two thirds in the other, each level of the tree would still move at most values, and the longest path down the tree would follow the larger parts. That path has as many levels as the times can be cut to two thirds before it reaches 1, which is about , 27 for 50,000 values. That is at most 1,350,000 moves, still .
The trouble comes when one part is almost as large as the whole list. If each call split off a single value, there would be levels instead of , and the work would be back to about .
Memory is the other cost. At any moment only the calls on the stack hold lists, and each of them holds a few lists, none longer than its own input. Those inputs have , , and so on values, which add up to less than , so the lists take extra memory. The stack holds one call for each merging level and one call on a single value, which is 17 frames for 50,000 values.
Time and memory of the two sorts
- Selection sort
time - A round removes one value, so there are rounds, with comparisons in all.
- Merge sort, time
- About levels, and each level moves all values once.
- Merge sort, memory
extra, stack about deep - The merged lists hold values, and each call's list is half of its caller's.
Deeper read: the cost of copying the halves
The slices a[:mid] and a[mid:] copy their values, so a call on values spends time on slicing. Its merge already costs that much, so the total stays .
Slicing does hurt when a call does only a constant amount of work of its own. A sum whose recursive case is return a[0] + total(a[1:]) copies values, then , and so on, which is 404,550 copies for a list of 900 numbers, a length that stays under the limit of 1,000 frames. A loop reads each number once. Passing an index, as in total(a, i), lets every call read the same list without copying it.
Divide and conquer in later lessons
Merge sort is the first of several algorithms with this plan. Quicksort puts the hard work in the divide step instead. It picks one value, the pivot, and splits the list into three groups: the values smaller than the pivot, the values equal to it, and the values larger than it. It sorts the smaller and the larger group with recursive calls, and the combine step only places the three groups side by side.
Some algorithms of this kind make only one recursive call. Binary search halves a sorted list and continues in one half only, so it has levels with a constant amount of work on each. Quickselect, which finds the th smallest value, splits a list around a pivot the way quicksort does and continues only on the side that holds that value. The Sorting and selection lesson teaches quickselect, together with a use of the merge that counts the pairs of values that are out of order.
Common mistakes in merge sort
Starting the right half one position too late.
- Where it breaks
- The right half starts at position
mid. Taken frommid + 1, it loses the value atmidat every split, and the eight values[38, 27, 43, 3, 9, 82, 10, 5]come back as[3, 5, 38, 82]. - The fix
- The left half is the positions before
mid, and the right half ismidand every position after it.
A base case for the empty list only.
- Where it breaks
- A list of one value splits into an empty list and itself.
merge_sort([5, 2])callsmerge_sort([5]), which callsmerge_sort([5])again, until the stack runs out. - The fix
- Return when the length is 1 or less. Those are the lengths that halving cannot make smaller.
Leaving out the values that remain after the merge loop.
- Where it breaks
- The loop stops as soon as one half is empty, and the rest of the other half is lost.
[2, 1]comes back as[1], and the eight values come back as[3]. - The fix
- After the loop, move the rest of the half that still has values to the output.
Recall Merge sort runs on 16 values. How many levels of its call tree merge, how many values do they move in total, and how deep does the stack get?
Halving 16 gives 8, 4, 2 and 1, so four levels merge. Each of them moves all 16 values, which is 64 moves in total. The stack is at most 5 calls deep: one call on each of the four merging levels and one on a single value.