Basics 0/97

Recursion · 3 of 3

Divide and conquer

Split an input in half, solve each half with a recursive call and combine the answers, with merge sort and its O(n log n) cost as the example.

2,023 words · 9 min read

Part 1 of 4 Divide and conquer

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.

Difficulty tier:Normal

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 O(nlog⁡n)O(n \log n) time and use as little extra space as possible.

Constraints

  • 1≤1 \le nums.length ≤5⋅104\le 5 \cdot 10^4
  • −5⋅104≤-5 \cdot 10^4 \le nums[i] ≤5⋅104\le 5 \cdot 10^4

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 nn values takes n−1n - 1 comparisons, the next round takes n−2n - 2, and so on. For the 50,000 values this problem allows, that is

(n−1)+(n−2)+⋯+1=n(n−1)2=50,000×49,9992=1,249,975,000 comparisons,\begin{aligned} (n - 1) + (n - 2) + \dots + 1 &= \frac{n(n - 1)}{2} \\ &= \frac{50{,}000 \times 49{,}999}{2} = 1{,}249{,}975{,}000 \text{ comparisons,} \end{aligned}

about 12 seconds at roughly 10810^8 simple operations a second.

Selection sort is slow because a round makes the problem only one value smaller, so it takes n−1n - 1 rounds, and a round reads most of the list. Merge sort makes the problem smaller much faster, by halving it:

  1. A list of one value, or of none, is already sorted. Return it.
  2. Split the list at its middle into a left half and a right half.
  3. Sort the left half with a recursive call.
  4. Sort the right half with a recursive call.
  5. 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.