Merge sort (Python)

From LiteratePrograms

Other implementations: ACL2 | C | C++ | dc | Eiffel | Erlang | Haskell | Java | JavaScript | Lisp | OCaml | Oz | Perl | Prolog | Python | Ruby | Scheme

This article explains how to implement merge sort in Python.

Conceptually, merge sort works as follows:

1. Divide the unsorted list into two sublists of about half the size
2. Sort each of the two sublists
3. Merge the two sorted sublists back into one sorted list.

The merge() method merges the two sorted sublists. The mergesort() method, which runs recursively, divides the unsorted lists into two sublists and sorts each sublist.

The merge() method

Given two sublists left and right, the merge() method merges two sublists into an ordered list. The result list contains the whole elements in both sublists. i is the index of the left list, and j is the index of the right list. We continually copy the smaller value between left[i] and right[j] into the result list and advance that value's index.

<<merge>>=
def merge(left, right):
    result = []
    i ,j = 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

When we met an end in either sublist, we simply copy the remaining portion to the result. Note that both left and right sublists are already in sorted order and we do not have to re-order the remaining portion of a sublist.

<<merge>>=
    result += left[i:]
    result += right[j:]
    return result

The mergesort() method

The mergesort() method is a recursive divide-and-conquer algorithm.

• Boundary condition: If an input has less than two elements, it simply returns the input because there is no need to sort less than two elements.
• Recursive condition: If an input has more than one elements, it divides the input into two sublists and recursively run mergesort() methods to sort each sublist. Then it merges two sublists using merge() method.

<<mergesort>>=
def mergesort(list):
    if len(list) < 2:
        return list
    else:
        middle = len(list) / 2
        left = mergesort(list[:middle])
        right = mergesort(list[middle:])
        return merge(left, right)

Here comes the whole source code with an integer list for an example.

<<mergesort.py>>=
merge
mergesort
if __name__ == "__main__":
    print mergesort([3, 4, 8, 0, 6, 7, 4, 2, 1, 9, 4, 5])

Execution result

crypto@crypto ~$ python mergesort.py
[0, 1, 2, 3, 4, 4, 4, 5, 6, 7, 8, 9]

Download code