Divide & Conquer

Example: Binary Search

Given sorted A[1..n] and number x. Find out whether A contains x.

Complexity:

Sorting

Input

Array A[1..n] of numbers

Output

Sorted A[1..n] in ascending order

Merge Sort

Merge

Suppose we have two sorted arrays:
B: 1, 5, 12
C: 2, 3, 7

and we want to combine the two arrays to get
1, 2, 3, 5, 7, 12

def merge(L, R):
    i = j = 0
    result = []
    while i < len(L) and j < len(R):
        if L[i] <= R[j]:
            result.append(L[i])
            i += 1
        else:
            result.append(R[j])
            j += 1
    while i < len(L):
        result.append(L[i])
        i += 1
    while j < len(R):
        result.append(R[j])
        j += 1
    return result

The complexity is

def merge_sort(A):
    if len(A) == 1:
        return A
    m = len(A) // 2
    L = merge_sort(A[:m])
    R = merge_sort(A[m:])
    return merge(L, R)