2.3 Designing Algorithms

You can choose from a wide range of algorithm design techniques. Insertion sort uses the incremental method: for each element $A[i]$, insert it into its proper place in the subarray $A[1:i]$, having already sorted the subarray $A[1:i-1]$.

This section examines another design method, known as “divide-and-conquer,” which we explore in more detail in Chapter 4. We’ll use divide-and-conquer to design a sorting algorithm whose worst-case running time is much less than that of insertion sort. One advantage of using an algorithm that follows the divide-and-conquer method is that analyzing its running time is often straightforward, using techniques that we’ll explore in Chapter 4.

2.3.1 The divide-and-conquer method¶

Many useful algorithms are recursive in structure: to solve a given problem, they recurse (call themselves) one or more times to handle closely related subproblems. These algorithms typically follow the divide-and-conquer method: they break the problem into several subproblems that are similar to the original problem but smaller in size, solve the subproblems recursively, and then combine these solutions to create a solution to the original problem.

In the divide-and-conquer method, if the problem is small enough -- the base case -- you just solve it directly without recursing. Otherwise -- the recursive case -- you perform three characteristic steps:

• Divide the problem into one or more subproblems that are smaller instances of the same problem.

• Conquer the subproblems by solving them recursively.

• Combine the subproblem solutions to form a solution to the original problem.

The merge sort algorithm closely follows the divide-and-conquer method. In each step, it sorts a subarray $A[p:r]$, starting with the entire array $A[1:n]$ and recursing down to smaller and smaller subarrays. Here is how merge sort operates:

Divide the subarray AŒp W r� to be sorted into two adjacent subarrays, each of half the size. To do so, compute the midpoint q of AŒp W r� (taking the average of p and r ), and divide AŒp W r� into subarrays AŒp W q� and AŒq C 1 W r�. Conquer by sorting each of the two subarrays AŒp W q� and AŒq C 1 W r� recursively using merge sort. Combine by merging the two sorted subarrays AŒp W q� and AŒq C 1 W r� back into AŒp W r�, producing the sorted answer. The recursion “bottoms out” -- it reaches the base case -- when the subarray AŒp W r� to be sorted has just 1 element, that is, when p equals r . As we noted in the initialization argument for I NSERTION-SORT’s loop invariant, a subarray comprising just a single element is always sorted. The key operation of the merge sort algorithm occurs in the <combine= step, which merges two adjacent, sorted subarrays. The merge operation is performed by the auxiliary procedure MERGE.A; p; q; r/ on the following page, where A is an array and p, q, and r are indices into the array such that p හ q < r . The procedure assumes that the adjacent subarrays AŒp W q� and AŒq C 1 W r� were al- ready recursively sorted. It merges the two sorted subarrays to form a single sorted subarray that replaces the current subarray AŒp W r�. To understand how the MERGE procedure works, let’s return to our card-playing motif. Suppose that you have two piles of cards face up on a table. Each pile is sorted, with the smallest-value cards on top. You wish to merge the two piles into a single sorted output pile, which is to be face down on the table. The basic step consists of choosing the smaller of the two cards on top of the face-up piles, removing it from its pile4which exposes a new top card4and placing this card face down onto the output pile. Repeat this step until one input pile is empty, at which time you can just take the remaining input pile and üip over the entire pile, placing it face down onto the output pile. Let’s think about how long it takes to merge two sorted piles of cards. Each basic step takes constant time, since you are comparing just the two top cards. If the two sorted piles that you start with each have n=2 cards, then the number of basic steps is at least n=2 (since in whichever pile was emptied, every card was found to be smaller than some card from the other pile) and at most n (actually, at most n  1, since after n  1 basic steps, one of the piles must be empty). With each basic step taking constant time and the total number of basic steps being between n=2 and n, we can say that merging takes time roughly proportional to n. That is, merging takes ‚.n/ time.

In detail, the MERGE procedure works as follows. It copies the two subarrays AŒp W q� and AŒq C 1 W r� into temporary arrays L and R (“left” and “right”), and then it merges the values in L and R back into AŒp W r�. Lines 1 and 2 compute the lengths nL and nR of the subarrays AŒp W q� and AŒq C 1 W r�, respectively. Then

line 3 creates arrays LŒ0 W nL  1� and RŒ0 W nR  1� with respective lengths nL and nR .12 The for loop of lines 435 copies the subarray AŒp W q� into L, and the for loop of lines 637 copies the subarray AŒq C 1 W r� into R. Lines 8318, illustrated in Figure 2.3, perform the basic steps. The while loop of lines 12318 repeatedly identiûes the smallest value in L and R that has yet to

be copied back into AŒp W r� and copies it back in. As the comments indicate, the index k gives the position of A that is being ûlled in, and the indices i and j give the positions in L and R, respectively, of the smallest remaining values. Eventually, either all of L or all of R is copied back into AŒp W r�, and this loop terminates. If the loop terminates because all of R has been copied back, that is, because j equals nR , then i is still less than nL , so that some of L has yet to be copied back, and these values are the greatest in both L and R. In this case, the while loop of lines 20323 copies these remaining values of L into the last few positions of AŒp W r�. Because j equals nR , the while loop of lines 24327 iterates 0 times. If instead the while loop of lines 12318 terminates because i equals nL , then all of L has already been copied back into AŒp W r�, and the while loop of lines 24327 copies the remaining values of R back into the end of AŒp W r�. To see that the MERGE procedure runs in ‚.n/ time, where n D r  p C 1,13 observe that each of lines 133 and 8310 takes constant time, and the for loops of lines 437 take ‚.nL C nR / D ‚.n/ time.14 To account for the three while loops of lines 12318, 20323, and 24327, observe that each iteration of these loops copies exactly one value from L or R back into A and that every value is copied back into A exactly once. Therefore, these three loops together make a total of n iterations. Since each iteration of each of the three loops takes constant time, the total time spent in these three loops is ‚.n/. We can now use the MERGE procedure as a subroutine in the merge sort al- gorithm. The procedure MERGE-SORT.A; p; r/ on the facing page sorts the ele- ments in the subarray AŒp W r�. If p equals r , the subarray has just 1 element and is therefore already sorted. Otherwise, we must have p < r , and MERGE-SORT runs the divide, conquer, and combine steps. The divide step simply computes an index q that partitions AŒp W r� into two adjacent subarrays: AŒp W q�, containing dn=2e elements, and AŒq C 1 W r�, containing bn=2c elements.15 The initial call MERGE-SORT .A; 1; n/ sorts the entire array AŒ1 W n�. Figure 2.4 illustrates the operation of the procedure for n D 8, showing also the sequence of divide and merge steps. The algorithm recursively divides the array down to 1-element subarrays. The combine steps merge pairs of 1-element subarrays

to form sorted subarrays of length 2, merges those to form sorted subarrays of length 4, and merges those to form the ûnal sorted subarray of length 8. If n is not an exact power of 2, then some divide steps create subarrays whose lengths differ by 1. (For example, when dividing a subarray of length 7, one subarray has length 4 and the other has length 3.) Regardless of the lengths of the two subarrays being merged, the time to merge a total of n items is ‚.n/.

2.3.2 Analyzing divide-and-conquer algorithms¶

When an algorithm contains a recursive call, you can often describe its running time by a recurrence equation or recurrence, which describes the overall running time on a problem of size $n$ in terms of the running time of the same algorithm on smaller inputs. You can then use mathematical tools to solve the recurrence and provide bounds on the performance of the algorithm.

A recurrence for the running time of a divide-and-conquer algorithm falls out from the three steps of the basic method. As we did for insertion sort, let T .n/ be the worst-case running time on a problem of size n. If the problem size is small enough, say n < n0 for some constant n0 > 0, the straightforward solution takes constant time, which we write as $\Theta(1)$.^[16] Suppose that the division of the problem yields a subproblems, each with size n=b, that is, 1=b the size of the original. For merge sort, both a and b are 2, but we’ll see other divide-and-conquer algorithms in which a ¤ b. It takes T .n=b/ time to solve one subproblem of size n=b, and so it takes aT .n=b/ time to solve all a of them. If it takes D.n/ time to divide the problem into subproblems and C.n/ time to combine the solutions to the subproblems into the solution to the original problem, we get the recurrence

Chapter 4: Divide-and-Conquer shows how to solve common recurrences of this form.

Sometimes, the $n/b$ size of the divide step isn’t an integer. For example, the Merge-Sort procedure divides a problem of size $n$ into subproblems of sizes $\lceil n / 2 \rceil$ and $\lfloor n/2 \rfloor$. Since the difference between $\lceil n/2 \rceil$ and $\lfloor n/2 \rfloor$ is at most 1, which for large $n$ is much smaller than the effect of dividing $n$ by 2, we’ll squint a little and just call them both size $n / 2$. As Chapter 4: Divide-and-Conquer will discuss, this simplification of ignoring floors and ceilings does not generally affect the order of growth of a solution to a divide-and-conquer recurrence.

Another convention we’ll adopt is to omit a statement of the base cases of the recurrence, which we’ll also discuss in more detail in Chapter 4. The reason is that the base cases are pretty much always T .n/ D ‚.1/ if n < n0 for some constant n0 > 0. That’s because the running time of an algorithm on an input of constant size is constant. We save ourselves a lot of extra writing by adopting this convention. Analysis of merge sort Here’s how to set up the recurrence for T .n/, the worst-case running time of merge sort on n numbers. Divide: The divide step just computes the middle of the subarray, which takes constant time. Thus, D.n/ D ‚.1/. Conquer: Recursively solving two subproblems, each of size n=2, contributes 2T .n=2/ to the running time (ignoring the üoors and ceilings, as we discussed). Combine: Since the MERGE procedure on an n-element subarray takes ‚.n/ time, we have C.n/ D ‚.n/. When we add the functions D.n/ and C.n/ for the merge sort analysis, we are adding a function that is ‚.n/ and a function that is ‚.1/. This sum is a linear function of n. That is, it is roughly proportional to n when n is large, and so merge sort’s dividing and combining times together are ‚.n/. Adding ‚.n/ to the 2T .n=2/ term from the conquer step gives the recurrence for the worst-case running time T .n/ of merge sort: T .n/ D 2T .n=2/ C ‚.n/ : (2.3)

Chapter 4: Divide-and-Conquer presents the “master theorem,” which shows that T .n/ D ‚.n lg n/.17 Compared with insertion sort, whose worst-case running time is ‚.n2 /, merge sort trades away a factor of n for a factor of lg n. Because the logarithm function grows more slowly than any linear function, that’s a good trade. For large enough inputs, merge sort, with its ‚.n lg n/ worst-case running time, outperforms insertion sort, whose worst-case running time is $\Theta(n^2)$.