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))