DS&A

Recursive Sorting

In the previous post we saw two iterative sorting algorithms: selection sort and insertion sort both work using a loop to put the right values in the right places, one at a time. They are two of the simplest sorting algorithms. But they’re not very efficient — for long lists, they’re too slow.(1)

In this post we’ll see one of the simplest efficient sorting algorithms, called merge sort. Rather than sorting items one-by-one, it works by recursively sorting shorter lists.

The strategy is:

1. Split the list data apart into two shorter lists,
2. Sort the shorter lists,
3. Put the data back together into one sorted list.

Step 2 is free — we just make a recursive call on each of the shorter lists. The hard work will either be in step 1 or step 3 — we must do some sorting either when we split the data apart, or when we put it back together again. Merge sort does the hard work in step 3.(2)

Merge sort

The merge sort algorithm begins by splitting the list into a first half and a second half. Both halves are sorted recursively; the hard work happens when we merge them back together. Try it out with the model below:

After splitting the list in two, we can make a “leap of faith” by trusting that the recursive calls will sort the shorter lists correctly.

Once both halves are sorted, we need to merge them back together; this is a subproblem. To build the output list, one value at a time, we must choose the smallest remaining value from one of the two halves. Since both halves are sorted, the smallest remaining value in each half is the first unused one.(3)

The algorithm sorts the output into a new list, so it is an “out-of-place” sort. Here’s an implementation in Python:

def merge_sort(lst):
    # if the list is this short, no sorting is necessary
    if len(lst) <= 1:
        # return a copy, out-of-place
        return list(lst)
    
    # half the length, rounded down
    m = len(lst) // 2
    
    # list slicing
    A = lst[:m]
    B = lst[m:]
    
    # sort both halves recursively
    A = merge_sort(A)
    B = merge_sort(B)
    
    return linear_merge(A, B)

def linear_merge(A, B):
    # merge two sorted lists
    output = []
    i, j = 0, 0
    
    while i + j < len(A) + len(B):
        if i < len(A) and (j == len(B) or A[i] <= B[j]):
            output.append(A[i])
            i += 1
        else:
            output.append(B[j])
            j += 1
    
    return output

Footnotes

1. We’ll do a proper analysis later.
2. Another efficient recursive sorting algorithm, quicksort, does the hard work in step 1 instead.
3. This solution is called a linear merge, hence the name merge sort.

• Tags: 
• recursion, divide and conquer, sorting, algorithms