### Preview lessons, content and tests

#### Computer Science & Programming solved. All in one platform.

1. To trial the platform and take tests, please take a few seconds to SIGN UP and SET UP FREE.
2. Searching for something specific? See our text overview of all tests. Includes 'real teacher' use videos.

Join 30000+ teachers and students using TTIO.

### 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

www.teachyourselfpython.com