5  Failures of Divide and Conquer Algorithms

In this section, we look at cases where D&C fails due to a failure of approach or execution.

Objectives: After learning this material, you should be able to:

• Given an incorrect D&C algorithm, explain why it fails.
• Given an incorrect D&C algorithm, construct an explicit example input where it fails and show how.

5.1 An Incorrect Mergesort

Sometimes, a tempting D&C solution doesn’t actually work. Other times, there are variants of correct solutions that have a mistake causing them to fail. By practicing to spot these errors, we can get a deeper understanding of Divide and Conquer as well as practice with an important Algorithms skill: constructing counterexamples.

Consider the following version of mergesort. What is the problem?

Algorithm 5.1 (Try to Mergesort)  

try_to_mergesort(A):
   if len(A) <= 1:
      return A
   let i = int(len(A)/2)
   let B = try_to_mergesort(A[0:i])
   let C = try_to_mergesort(A[i+1:end])
   return (B,C)     # list B followed by list C

The difference is in the last line: instead of using merge(B,C), we simply concatenate B and C together.

If you understood mergesort completely, you might feel that it’s obvious that this code will fail. But can you prove that it’s wrong?

Proving incorrectness. The property of correctness is a “for all” statement: for every input, the algorithm produces a correct output. Therefore, the property of “not correct” is a “there exists” statement: there exists an example where the algorithm produces an incorrect output. To prove incorrectness, all you need to do is give an single input and show why the algorithm produces an incorrect output.

Proposition 5.1 Algorithm alg. 5.1 is incorrect.

Proof. Consider the input A = [8,3]. We claim that the algorithm outputs [8,3], which is not sorted, so it is an incorrect output.

On input A = [8,3], the algorithm first splits [8] and [3] and recursively calls itself on each, resulting in B = [8] and C = [3]. It then concatenates them together, resulting in B followed by C, which is [8,3]. This output is not sorted.

5.2 Another Incorrect Mergesort

Let’s try again. What is the problem here?

Algorithm 5.2 (Try Again to Mergesort)  

try_again_mergesort(A):
    if len(A) <= 1:
       return A
    let i = int(len(A)/2)
    let B = try_again_mergesort(A[0:i])
    let C = A[i+1:end]
    return merge(B,C)

Exercise 5.1 Prove that alg. 5.2 is incorrect.

Example solution.

Aside. The problem is that we only recursively sort B, but not C. That means that C may not be correctly sorted, leading to an incorrect result. But again, to prove it, we have to give a concrete example.

Proof. Consider the input A = [1,2,4,3]. We claim the output will be [1,2,4,3], which is not correctly sorted.

First, the algorithm divides A into [1,2] and [4,3]. Then, it recursively calls itself on B, which we can check will return B = [1,2]. Then it will merge B = [1,2] and C = [4,3]. Recalling how merge works, it will start from the beginning of each array and take the smaller element, so it will produce [1,2,4,3].