#!/usr/bin/env python
import time

def merge_sort(a):
    if len(a) == 1:
        return a
    else:
        lower = merge_sort(a[:len(a)//2])
        upper = merge_sort(a[len(a)//2:])
        return merge(lower, upper)

def merge(low, up):
    ret = []
    i, j = 0, 0
    while i < len(low) and j < len(up):
        if low[i] <= up[j]:
            ret.append(low[i])
            i += 1
        else:
            ret.append(up[j])
            j += 1
    ret += low[i:]
    ret += up[j:]
    return ret

def qsort(a):
    if a == []:
        return []
    else:
        pivot = a[0]
        lesser = qsort([x for x in a[1:] if x < pivot])
        greater = qsort([x for x in a[1:] if x >= pivot])
        return lesser + [pivot] + greater

def measure(fun, param):
    t0 = time.time()
    print(fun(param))
    elapsed = time.time() - t0
    print(fun.__name__ + ": " + str(elapsed) + " s")

if __name__ == "__main__":
    a = [3, 5, 2, 6, 4, 2, 6, 21, 65, 1, 10, 7, 4, 9, 8]

    measure(merge_sort, a)
    measure(qsort, a)