Divide and Conquer

You and a friend each rank the same six films. You want one number that says how much you disagree. A natural one: count the pairs of films you put in opposite order. If you rank Film A above Film B and your friend ranks B above A, that pair is one disagreement.

Number the films 1 to 6 in your order. Then write your friend's list, favourite first, using your numbers: [3, 6, 5, 1, 4, 2]. A disagreement is any bigger number that appears before a smaller one. Checking every pair works, but that is n(n − 1) / 2 comparisons, about 45 billion for a catalogue of 300,000 films. Divide and conquer does it in O(n log n).

#The idea: split, solve, combine

You have already met this pattern twice. Binary search throws away half the range and solves the other half. Merge sort sorts each half and merges them. Both follow the same three steps:

1. Divide the input into smaller parts, usually two halves.
2. Conquer each part by calling the same function on it.
3. Combine the answers for the parts into the answer for the whole.

The first two steps are almost free to write. All the thinking goes into the combine step: given the answers for each half, what is still missing, and how do you get it cheaply?

#Counting disagreements

Split the list into [3, 6, 5] and [1, 4, 2]. Every disagreement is one of three kinds: both numbers in the left half, both in the right half, or one in each. The recursive calls count the first two kinds. The combine step only has to count the pairs that cross the middle.

Counting crossing pairs one by one would still be slow. Here is the trick: the crossing count does not depend on the order inside each half. So you are free to sort each half first, and the recursion can hand back sorted halves for nothing, because merging them is exactly what merge sort does anyway.

During the merge, every left item came before every right item in your friend's list. So when a right item is smaller than the front of the left half, it is also smaller than everything still waiting there, and each of those is a disagreement. Add how many are waiting, in one step.

merge left and right, counting as you go:while both halves have items:  if left[i] <= right[j]:    take left[i]  else:    cross += items still waiting in left    take right[j]copy whatever remains

// Returns [sorted copy of a, number of disagreements in a].
function sortAndCount(a) {
  if (a.length <= 1) return [a, 0];
  const mid = Math.floor(a.length / 2);
  const [left, leftCount] = sortAndCount(a.slice(0, mid));
  const [right, rightCount] = sortAndCount(a.slice(mid));
  const merged = [];
  let i = 0, j = 0, cross = 0;
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      merged.push(left[i++]);
    } else {
      cross += left.length - i; // right[j] jumps every waiting left item
      merged.push(right[j++]);
    }
  }
  while (i < left.length) merged.push(left[i++]);
  while (j < right.length) merged.push(right[j++]);
  return [merged, leftCount + rightCount + cross];
}
 
sortAndCount([3, 6, 5, 1, 4, 2])[1]; // 10

# Returns (sorted copy of a, number of disagreements in a).
def sort_and_count(a):
    if len(a) <= 1:
        return a, 0
    mid = len(a) // 2
    left, left_count = sort_and_count(a[:mid])
    right, right_count = sort_and_count(a[mid:])
    merged = []
    i = j = cross = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            cross += len(left) - i  # right[j] jumps every waiting left item
            merged.append(right[j])
            j += 1
    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged, left_count + right_count + cross
 
sort_and_count([3, 6, 5, 1, 4, 2])[1]  # 10

Note the <=. When two values are equal, take the left one first. They are not a disagreement, so nothing should be counted for them.

#Reading the cost of any split

You do not need a formula to price a divide and conquer algorithm. Draw the tree of calls and add up the work level by level. Two things decide the answer: how many smaller calls each call makes, and how much the combine step costs.

#One half is enough: fast power

Sometimes the two halves are the same problem, so you solve it once. To compute 3¹³, note that 3¹³ = 3⁶ × 3⁶ × 3. And 3⁶ = 3³ × 3³, and so on. Each call halves the exponent and does one or two multiplications.

// x to the power n, for a whole number n >= 0
function power(x, n) {
  if (n === 0) return 1;
  const half = power(x, Math.floor(n / 2)); // solve the half once
  return n % 2 === 0 ? half * half : half * half * x;
}
 
power(3, 13); // 1594323

# x to the power n, for a whole number n >= 0
def power(x, n):
    if n == 0:
        return 1
    half = power(x, n // 2)  # solve the half once
    return half * half if n % 2 == 0 else half * half * x
 
power(3, 13)  # 1594323

The exponent goes 13, 6, 3, 1, 0: five calls and 7 multiplications, where a plain loop needs 12. For an exponent of a billion, 31 calls. That is the first row of the table: one call on half, constant combine, O(log n).

#Common mistakes

#Check yourself

#What to practise next

Quicksort is divide and conquer with the work moved to the divide step. Next in this module, Intervals puts sorting to work on ranges of time.