Combsort

Combsort gehört zur Gruppe der asymptodisch guten Sortieralgorithmen. Er ist in gewisser Weise eine optimierte Variante von Ripplesort (analog zu Shellsort und Insersort)

Da intern Ripple, Bubblesort oder Oetsort verwendet wird, kann dieser Algorithmus gleichzeitig zur Gruppe der umhüllenden Sortieralgorithmen gezählt werden.

Combsort ist der einzige Algorithmus, der sich eindeutig aus einem elementaren Sortierverfahren (Ripplesort) ableiten läßt, seine Einfachheit nahezu beibehält, aber fast eine optimale Laufzeit erreicht. Er ist iterativ und ohne zusätzlichen Speicherplatz realisierbar. Im "Preis-Leistungs-Verhältnis" ist dieser Algorithmus Shellsort ebenwürdig.

Der Name "Combsort" kommt von comb (dt. Kamm, kämmen), da das Feld (2D) mit einem immer feiner werdenden Kamm durchkämmt wird.

Die Idee wurde erstmalig von Richard Box und Stephen Lacey vorgestellt (April 1991).