funnel_sort.py

def split_into(ls, k):
    output = []
    for i in range(k):
        output.append([])
    i = 0
    for item in ls:
        output[i % k].append(item)
        i += 1
    return output

def binary_merge(a, b):
    i = 0
    j = 0
    output = []
    while i + j < len(a) + len(b):
        if i >= len(a):
            output.append(b[j])
            j += 1
        elif j >= len(b):
            output.append(a[i])
            i += 1
        elif a[i] <= b[j]:
            output.append(a[i])
            i += 1
        else:
            output.append(b[j])
            j += 1
    return output

def funnel_merge(ls):
    k = len(ls)
    rootk = int(k ** 0.5)

    if k == 1:
        return ls[0]
    elif k == 2:
        return binary_merge(ls[0], ls[1])
    elif k == 3:
        return binary_merge(binary_merge(ls[0], ls[1]), ls[2])
    else:
        subtrees = split_into(ls, rootk)
        results = []
        for subtree in subtrees:
            results.append(funnel_merge(subtree))
        return funnel_merge(results)

def funnel_sort(l):
    n = len(l)
    smalln = int(n ** (1.0 / 3.0))

    print(n, smalln)
    if n  < 2**3:
        # Too small to funnel sort again, so just use any sort
        l.sort()
        return l
    else:
        subarrays = split_into(l, smalln)
        results = []
        for subarray in subarrays:
            results.append(funnel_sort(subarray))
        return funnel_merge(results)