Use of Divide and Conquer

We begin looking at algorithms, sorted by the techniques they use.

The first is divide and conquer:

• Divide problem into smaller problems.
• Recursively solve these.
• Combine solutions to find answer.

Sorting

Problem class SORT:

Input: an array a of integers.

Output: an array with all elements of a in increasing order.

example:

        +----+----+----+----+----+----+----+----+
    a = | 19 |  1 | 29 | 30 |  6 | 15 |  2 |  5 |
        +----+----+----+----+----+----+----+----+

        +----+----+----+----+----+----+----+----+
 return |  1 |  2 |  5 |  6 | 15 | 19 | 29 | 30 |
        +----+----+----+----+----+----+----+----+

MergeSort

Algorithm Merge-Sort(a)
if a's length > 1 then
  x <- first half of a
  y <- second half of a
  Merge-Sort(x)
  Merge-Sort(y)
  a <- Merge(x, y)
fi

example:

                           |  +----+----+----+----+----+----+----+----+
                           |  |  1 |  2 |  5 |  6 | 15 | 19 | 29 | 30 |
                           |  +----+----+----+----+----+----+----+----+
                           |
        +----+----+----+----+----+----+----+----+
        | 19 |  1 | 29 | 30 |  6 | 15 |  2 |  5 |
        +----+----+----+----+----+----+----+----+
                      |           |
+----+----+----+----+ |           |  +----+----+----+----+
|  1 | 19 | 29 | 30 | |           |  |  2 |  5 |  6 | 15 |
+----+----+----+----+ |           |  +----+----+----+----+
                      |           |
     +----+----+----+----+     +----+----+----+----+
     | 19 |  1 | 29 | 30 |     |  6 | 15 |  2 |  5 |
     +----+----+----+----+     +----+----+----+----+
            |    |                          |   |            
+----+----+ |    | +----+----+  +----+----+ |   | +----+----+
| 19 |  1 | |    | | 29 | 30 |  |  6 | 15 | |   | |  2 |  5 |
+----+----+ |    | +----+----+  +----+----+ |   | +----+----+
            |    |                          |   |            
  +----+----+    +----+----+      +----+----+   +----+----+
  | 19 |  1 |    | 29 | 30 |      |  6 | 15 |   |  2 |  5 |
  +----+----+    +----+----+      +----+----+   +----+----+
     /   \         /     \         /      \        |      \
+----+  +----+  +----+  +----+  +----+  +----+   +----+  +----+
| 19 |  |  1 |  | 29 |  | 30 |  |  6 |  | 15 |   |  2 |  |  5 |
+----+  +----+  +----+  +----+  +----+  +----+   +----+  +----+

Merging

Algorithm Merge(x, y)
x_pos <- 0, y_pos <- 0, a_pos <- 0
while x_pos < x.length and y_pos < y.length do
  if x[x_pos] < y[y_pos] then
    a[a_pos] <- x[x_pos]
    x_pos <- x_pos + 1
  else
    a[a_pos] <- y[y_pos]
    y_pos <- y_pos + 1
  fi
  a_pos <- a_pos + 1
od
append x[x_pos...x.length] to a
append y[y_pos...y.length] to a
return a

example:

 +----+----+----+----+
 |  1 | 19 | 29 | 30 |
 +----+----+----+----+\    +----+----+----+----+----+----+----+----+
                       >-->|  1 |  2 |  5 |  6 | 15 | 19 | 29 | 30 |
 +----+----+----+----+/    +----+----+----+----+----+----+----+----+
 |  2 |  5 |  6 | 15 |
 +----+----+----+----+

How Much Time?

Write a recurrence.

   T(n) = 2 T(n / 2) + O(n)

The Master Theorem (p 73) solves this. For T(n) = a T(n / b) + f(n):

• if f(n) = O(n^(log_b a - eps)) for some eps > 0, then T(n) = O(n^(log_b a))
• if f(n) = O(n^(log_b a)), then T(n) = O(n^(log_b a) log n)

For Merge-Sort, then, where a = 2 and b = 2