Code: Alles auswählen
from collections import deque
from heapq import merge
def XYsort(seq):
if len(seq) <= 1:
return seq
items = iter(seq)
slist = deque([items.next()])
ulist = []
for item in items:
if item < slist[0]:
slist.appendleft(item)
elif not item < slist[-1]:
slist.append(item)
else:
ulist.append(item)
return merge(slist, XYsort(ulist))
print list(XYsort([7, 8, 9, 4, 5, 6, 1, 2, 3, 0]))Offensichtlich ist er verwandt mit Natural Mergesort, aber doch anders. Die Idee ist, eine zu sortierende Liste in je eine sortierte und eine unsortierte zu splitten, das ganze rekursiv auf die neu gewonnene unsortierte Liste anzuwenden, und das Ergebnis mit der sortierten Liste zu mergen. AFAICS ist er stabil, obwohl ich noch nicht ausgiebig drüber nachgedacht habe, und für verkettete Listen ist er in-place. Best Case ist O(n), Avarage Case ist O(n log n) und Worst Case ist O(n^2), weil dabei pro rekursivem Aufruf nur je zwei Elemente abgezwickt werden, und beim Mergen viele unnütze Vergleiche durchgeführt werden müssen. Man kann ihn aber mit Quicksort kombinieren, dann werden die jeweiligen Worst Cases abgefangen.
