Chapter 5

Section 5.1 introduces the divide and conquer style of algorithmic problem solving with the Merge-Sort algorithm. The algorithm can be represented by the following recurrence equation: T(n) = 2T(n/2) + cn for all n > 2. This algorithm basically splits the list of items down recursively until it gets to a “base case” where there are only one or two items. The comparison at this point is a simple greater than or less than. The sorted pieces are then combined back together into a full list. The runtime of this algorithm is O(nlogn).

I give this chapter a 6 for readability and a 6 on the interesting scale.