qsort.py

from collections import defaultdict

def splitter(l, mapper):
    """Partition an iterable by a callable mapper."""

    results = defaultdict(list)

    for x in l:
        results[mapper(x)].append(x)

    return results


def qsort(l):
    """QuickSort an iterable."""

    if len(l) <= 1:
        return l

    pivot = l[0]
    split = splitter(l, lambda x: cmp(x, pivot))

    return qsort(split[-1]) + split[0] + qsort(split[1])


def qsort2(l):
    """QuickSort an iterable."""

    if len(l) <= 1:
        return l

    pivot = l[0]
    result = [
        y
        for partition, x in splitter(l, lambda x: cmp(x, pivot)).items()
        for y in (qsort2(x) if partition else x)
    ]

    return result


def qsort3(l):

    if len(l) <= 1:
        return l

    less = []
    pivots = []
    more = []

    pivot = l[0]
    for x in l:
        (less if x < pivot else more if x > pivot else pivots).append(x)

    return qsort3(less) + pivots + qsort3(more)