5.3.1. Mergesort Concepts¶

A natural approach to problem solving is divide and conquer. To use divide and conquer when sorting, we might consider breaking the list to be sorted into pieces, process the pieces, and then put them back together somehow. A simple way to do this would be to split the list in half, sort the halves, and then merge the sorted halves together. This is the idea behind Mergesort.

Mergesort is one of the simplest sorting algorithms conceptually, and has good performance both in the asymptotic sense and in empirical running time. Unfortunately, even though it is based on a simple concept, it is relatively difficult to implement in practice. Here is an example implementation of Mergesort in Python:

def mergesort(inlist):
    if len(inlist) <= 1:
        return inlist
    l_1 = inlist[len(inlist) // 2 :]    # half of the items from inlist
    l_2 = inlist[: len(inlist) // 2]    # other hald of the items
    return merge(mergesort(l_1), mergesort(l_2))

Here is a visualization that illustrates how Mergesort works.

The hardest step to understand about Mergesort is the merge function. The merge function starts by examining the first record of each sublist and picks the smaller value as the smallest record overall. This smaller value is removed from its sublist and placed into the output list. Merging continues in this way, comparing the front records of the sublists and continually appending the smaller to the output list until no more input records remain.

Here is an implementation in Python for merge on lists:

def merge(l_1, l_2):
    answer = []
    while l_1 or l_2:
        if not l_1:     # l_1 is empty, append rest items from l_2
            answer += l_2
            break
        elif not l_2:   # l_2 is empty, append rest items from l_1
            answer += l_1
            break
        elif l_1[0] <= l_2[0]:
            answer.append(l_1.pop(0))
        else:
            answer.append(l_2.pop(0))
    return answer

Here is a visualization for the merge operation.

Settings

Saving...
Server Error
Resubmit

This visualization provides a running time analysis for Merge Sort.

Settings

Saving...
Server Error
Resubmit