Algorithm Design paradigms — Divide and Conquer

One of the most powerful and ubiquitous technique for solving complex problems is to break them down into smaller problems. Firstly, and more naturally, smaller problems are less overwhelming. Secondly, and more importantly, they permit us to focus on the details that were not so obvious while working with a big problem. Two important algorithm design paradigms based on breaking problems into smaller problems are — Dynamic programming and Divide and Conquer. In this article we’ll focus on the latter saving former one for some other time.

Divide and Conquer splits the problem in halves, solves each half, then stitches the pieces back together to form a full solution.

More generally, to use divide and conquer we must divide the problem into two smaller sub problems, solve each of them recursively and finally merge the two partial solutions into one grand solution to the full problem. Whenever the merging step takes less time than solving sub problems, we get an efficient solution.

Applying it in practice could be as simple as Binary search or as complex as Merge sort. Let’s explore the magic of divide and conquer at both ends of spectrum.

Binary Search

Animation of binary search

Binary Search is an efficient algorithm for searching element in a sorted array. It first compares the search key with middle element of an array. If search key is less than middle element, later half of array is discarded for further search. Similarly, if key is greater than middle element, first half of array is ignored. Picture at left shows how search proceeds for key 68.

Notice that every comparison of binary search halves the further search space. Thus the number of times we can halve n until we get to 1 is log n. Consequently, binary search takes O(log n) time in worst case.

def binary_search(arr, low, high, key):
    while low <= high:
        mid = low + (high - low)/2
        if arr[mid] == key:
            return mid
        elif arr[mid] < key:
            low = mid + 1
        else:
            high = mid - 1
    return -1

Merge Sort

Like binary search, merge sort is another Divide and Conquer algorithm, albeit a complex one. The algorithm is called merge sort, recognizing the importance of the interleaving operation.

def merge_sort(arr[1, n]):
    merge(merge_sort(arr[1, n/2]), merge_sort(arr[n/2 + 1, n]))

Base case of this recursion occurs when sub array to be sorted consists of a single element.

Merge sort animation

Efficiency of merge sort depends upon how efficiently we combine the two sorted halves into single sorted list. Observe that smallest overall item in two lists sorted in ascending order must sit at the top of one of the two lists. Removing this smallest elements leaves us with two sorted list — one slightly shorter than before. Again, second smallest element overall must be sit at top of one of these lists. Repeating the same operation till both lists are empty merges these two lists into single sorted list.

Notice that number of elements in a sub problem are getting halved at each level. Thus number of times we can halve n until we get to 1 is log n. Since the recursion goes log n level deep, and linear amount of work is done at each level (merging the two lists), merge sort takes O(n log n) time in worst case.

def merge_sort(arr):
    print("Splitting ", arr)
    if len(arr) > 1:
        mid = len(arr)//2
        left_half = arr[:mid]
        right_half = arr[mid:]
        merge_sort(left_half)
        merge_sort(right_half)
        merge(left_half, right_half)

Again, challenging part is how we merge two sorted list. Only issue is we must put our merged array somewhere. To avoid losing an element by over writing it while merging, we first copy each sub array to a separate list and merge those elements safely back into the array.

def merge(left_half, right_half):
    i = 0
    j = 0
    k = 0
    while i < len(left_half) and j < len(right_half):
        if left_half[i] < right_half[j]:
            arr[k] = left_half[i]
            i = i + 1
        else:
            arr[k] = right_half[j]
            j = j + 1
        k = k + 1
    while i < len(left_half):
        arr[k] = left_half[i]
        i = i + 1
        k = k + 1
    while j < len(right_half):
        arr[k] = right_half[j]
        j = j + 1
        k = k + 1
    print("Merging ",arr)

Lastly, divide and conquer is a design technique with many important algorithms to its credit. However, beyond binary search and it’s variants, I find it to be difficult design paradigm to apply in practice.

Please let me know through your comments any modifications/improvements needed in the article.