merge_sort.py

# encoding: utf-8
import math


def merge_sort(t):
    if len(t) <= 1:
        return t
    else:
        t1, t2 = split(t)
        t1 = merge_sort(t1)
        t2 = merge_sort(t2)
        return merge(t1, t2)


def split(t):
    if len(t) <= 1:
        return t
    else:
        mid = math.floor(len(t) / 2)
        t1 = t[:mid]
        t2 = t[mid:]
        return t1, t2


def merge(t1, t2):
    if len(t1) == 0:
        return t2
    elif len(t2) == 0:
        return t1
    elif t1[0] > t2[0]:
        return [t2[0]] + merge(t1, t2[1:])
    else:
        return [t1[0]] + merge(t1[1:], t2)