Bitonicsort

Bitonicsort gehört zur Gruppe der asymptodisch guten Sortieralgorithmen. Er funktioniert ähnlich Mergesort, realisiert "merge" allerdings völlig anders.

Bitonicsort bietet den großen Nachteil, daß er nur ein Feld sortieren kann, das n Elemente besitzt, wobei n eine 2er-Potenz sein muß. Dieses Problem kann beseitigt werden, in dem zuerst das größte Element ermittelt wird (einmal das gesamte Feld durchlaufen) und das Feld anschließend mit diesem Element (oder +unendlich) aufgefüllt wird, bis genügend Elemente enthalten sind. Dann wird dieses Feld sortiert und anschließend die vorher hineingesteckten Elemente wieder entfernt.

Bitonicsort bietet den Vorteil, daß es Mergesort sehr ähnlich und daher relativ unabhängig von den zu sortierenden Werten ist. Daher ist dieses Verfahren auch gut mit einer entsprechenden Hardware realisierbar.

Der Name "Bitonicsort" kommt von bi und tonic (dt. zwei, tonisch) und spielt auf seinen bitonischen Lauf (ein Teilstück aufwärts, das andere abwärts sortiert) an.