Stabiler Sortieralgorithmus

Ein Sortieralgorithmus wird als stabil bezeichnet, wenn die Reihenfolge von Elementen mit gleichen Sortierschlüssel bewahrt bleibt. Dies hört sich vielleicht reicht unverständlich an, ist aber recht einfach zu verstehen. Die Definition besagt nur, dass wenn man zum Beispiel zwei Elemente mit gleichem Wert hat, diese Elemente nicht vertauscht werden. Oder besser gesagt, zwei Elemente mit gleichem Wert haben vor der Sortierung und nach der Sortierung die gleiche Reihenfolge.

Ein klassisches Beispiel für einen stabilen Sortieralgorithmus ist Bubblesort. Weitere Beispiele sind Insertionsort, Mergesort, Countingsort, Radixsort und Bucketsort. Ein Beispiel für einen instabilen Sortieralgorithmus ist Heapsort.