Das deutsche Python-Forum

Code: Alles auswählen

from collections import deque
from itertools import chain, islice
from heapq import merge


def micksort(unsorted):

    def sort2(a, b):
        return [b, a] if b < a else [a, b]

    def sort3(a, b, c):
        if b < a: a, b = b, a
        if c < b: b, c = c, b
        if b < a: a, b = b, a
        return [a, b, c]

    def sortn(seq):
        n = len(seq)
        if n <= 1: return seq
        if n == 2: return sort2(*seq)
        if n == 3: return sort3(*seq)
        return sort(seq)

    def sort(seq):
        items = iter(seq)
        smallest, pivot, biggest = sort3(*islice(items, 3))
        msmalls, mbigs = deque([smallest, pivot]), [biggest]
        qsmalls, qbigs = [], []
        for item in items:
            if not item < biggest:
                mbigs.append(item)
                biggest = item
            elif item < smallest:
                msmalls.appendleft(item)
                smallest = item
            elif item < pivot:
                qsmalls.append(item)
            elif pivot < item:
                qbigs.append(item)
            else:
                msmalls.append(item)
        return chain(merge(msmalls, sortn(qsmalls)), merge(mbigs, sortn(qbigs)))

    return list(sortn(unsorted))