merge_sort.py

#! /usr/bin/env python
# coding: utf-8
"""
Copyright 2014 Tatsuro Yasukawa.

Distributed under the GNU General Public License at
gnu.org/licenses/gpl.html.
"""

def merge(x,y):
    """
    >>> x,y = [2],[5]
    >>> merge(x,y)
    [2, 5]
    >>> x = [2, 5]
    >>> y = [4, 6]
    >>> merge(x,y)
    [2, 4, 5, 6]
    """
    i = j = 0
    t = []
    while i < len(x) and j < len(y):
        if x[i] < y[j]:
            t.append(x[i])
            i += 1
        else:
            t.append(y[j])
            j += 1
    if not i < len(x):
        t.extend(y[j:])
    else:
        t.extend(x[i:])
    return t

def merge_sort(t):
    """
    >>> t = [3,5,6,9,4,6,7,8,2,9,1,2]
    >>> merge_sort(t)
    [1, 2, 2, 3, 4, 5, 6, 6, 7, 8, 9, 9]
    """
    if len(t) < 2: return t
    i = len(t)/2
    return merge(
        merge_sort(t[:i]),
        merge_sort(t[i:])
    )