**1.** To trial the platform and take tests, please take a few *seconds* to ** SIGN UP
** and SET UP FREE.

Join **
30000+
** teachers and students using TTIO.

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.

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

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

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

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