Merge Sort

Today, I will describe a new sorting algorithm: Merge Sort, a divide-and-conquer algorithm invented by John von Neumann in 1945. The general idea of merge sort is: when you solve a problem, if you can split the problem into two halves, solve each of them, one at a time (which is most likely easier because the problem in each half gets smaller.) And most importantly, if we have the answer for both halves, there is a simple and easy way to MERGE these two results into the result of the big problem.

First, we notice that when we have 2 sorted arrays, we can easily merge these two sorted arrays into one big sorted array. Here is a simple procedure: We simply just need to compare the first element at each of the 2 arrays. We will remove the smaller element and put it into a separate array. Continue until both arrays are empty.

Code

Here is the pseudo-code for merging 2 sorted arrays into one:

def merge_2_arr(a1,a2):
    final = []
    l1 = len(a1)
    l2 = len(a2)
    h1 = 0
    h2 = 0
    while h1 < l1 and h2 < l2:
        if a1[h1] < a2[h2]:
            final.append(a1[h1])
            h1 += 1
        else:
            final.append(a2[h2])
            h2 += 1
            
    if h1 < l1:
        for i in range(h1,l1):
            final.append(a1[i])
            
    elif h2 < l2:
        for i in range(h2,l2):
            final.append(a2[i])
    
    return final

Now we know how to merge 2 sorted arrays into a big, sorted one. The idea of Merge Sort is to split the array into 2 halves, sort each half and merge them into one sorted array. The question is how to sort each half. We notice that we have the same sorting problem. The only difference is that the sorting size is half of the original. But we still do not know how to sort a small array. The only exception is when the size of the array is 1. It contains a single number and, of course, sorted. Ah-ha! We can continue to divide the array until the array’s size is 1.

Here’s the code:

def merge_sort(a):
    if len(a) == 1:
        return a
    middle = int(len(a)/2)
    a1 = merge_sort(a[0:middle])
    a2 = merge_sort(a[middle:])
    final = merge_2_arr(a1,a2)
    return final

Complexity Analysis

We want to find how many operations this algorithm takes to sort an array of length n. We will cover this in the next write-up. See you soon!!!