Divide and conquer deals with breaking inputs into parts, solving recursively, and then combining solutions.

Mergesort sorts a given list of numbers by first dividing them into two equal halves, sorting each half separately by recursion, and then combining the results of these recursive calls using the linear-time algorithm for merging sorted lists.

Two ways to find solutions for recurrence: The first is to ‘unroll’ the recursion and identify a pattern. The sum of the running times over all levels of recursion arrive at a running time. The second is to begin with a guess, substitute it into the recurrence relation, and verify.

Unrolling the Mergesort Recurrence: At first level, the problem is size n (cn + subsequent calls). The next level has two problems with size n/2 (cn/2 + subsequent calls), then four problems with size n/4 (cn/4 + sub calls), etc. The pattern is defined by n/2^j (j = level). Thus level j contributes 2^j(cn/2^j) = cn to the running time. The total running time for the algorithm is O(n log n).

In the case of a tree where q > 2 (q being number of children), the work increases with every level of recursion. This gives q^j instances at level j. A function with q > 2 is bounded by O(n^log2(q)). For example, when q=2, running time is O(n^4).

Consider the case where q=1. The work per level decreases with recursion. At an arbitrary level j, it contributes cn/2^j to the run time. A function with q=1 is bounded by O(n) run time.

q = 1: O(n) - linear q = 2: O(n log n) q > 2: polynomial with exponent > 1

An inversion occurs when an ordering of numbers has numbers out of order. There may be a quadratic number of inversions for each set of numbers. The algorithm is similar to Mergesort except we count inversions along with sorting the list. Recursively divide the list and sort separate halves. Compare the sorted halves against each other for inversions.

When merging the list, we compare elements in subsets A and B. If the element in A is smaller, it is appended to the new list and no inversions occur. If B is smaller, it is appended to the list and the number of remaining elements in A is the number of inversions because they come before elements in B. This is the Sort-and-Count algorithm runs in O(n log n) time.

Given n points in the plane, find the pair that is closest together. This is done by dividing and comparing the closest points in each half. We sort the points by the x- and y-coordinates in two separate lists. The two lists are divided again into left and right sides of the plane. Determine a closest pair of points on each side. If there exists a pair of points, each in a separate set, with a smaller distance than that found in the respective subsets ($), then each of the point lies within $ of the dividing line. Following this logic, we need only search the points within $ of the dividing line for a better result than the separate sets of points. The running time of the algorithm is O(n log n).