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)
