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).