Overview of Merge Sort

Because we're using divide-and-conquer to sort, we need to decide what our subproblems are going to look like. The full problem is to sort an entire array. Let's say that a subproblem is to sort a subarray. In particular, we'll think of a subproblem as sorting the subarray starting at index p and going through index r. It will be convenient to have a notation for a subarray, so let's say that $array[p \cdots r]$ denotes this subarray of array. Note that this "three-dot" notation is not legal; we're using it just to describe the algorithm, rather than a particular implementation of the algorithm in code. In terms of our notation, for an array of  ...