Jeder, der schon einmal erfolgreich eine Telefonnummer in einem Telefonbuch gesucht hat, weiß, dass es sinnvoll sein kann gewisse Dinge zu sortieren. Auch in Lexika macht eine Sortierung Sinn. Da das Sortieren für den Menschen eher eine Stumpfsinnige Arbeit ist, liegt es nahe, es dem Rechner zu überlassen. Im Laufe der Zeit wurden viele verschiedene Sortieralgorithmen entwickelt. Einige sollen nun vorgestellt werden.

• Auswahl 1 (2 Reihungen)
• Auswahl 2 (1 Reihung)
• Einfügen
• Bubblesort
• Quicksort
• Heapsort, Shellsort, Bucketsort, Platzziffersortieren, Mergesort

Die Auswahl-Sortierverfahren heißen je nach dem auch Minsort, Maxsort bzw. Selectionsort.

Es gibt verschiedene Kriterien, die die Anwendung verschiedener Verfahren notwendig machen.

Wird nicht eine einfache Liste von Worten oder Zahlen sortiert, sondern beispielsweise eine Tabelle mit mehreren Spalten, so kann es wichtig sein, die schon vorhandene Sortierung nach Buchtiteln nicht zu zerstören, wenn die Tabelle nach Verlagen sortiert werden soll. Die Folge eines stabilen Verfahrens wäre also eine Liste, die nach Verlagen sortiert ist. Die Einträge eines jeweiligen Verlages sind nach Buchtiteln sortiert.

Quicksort ist beispielsweise nicht stabil. Liegt eine Reihung von Zahlen vor und die beispielsweise die 4 kommt mehrfach vor, dann kann sich die Reihenfolge der 4en innerhalb der Reihung während des Sortiervorgangs verändern. Wird Bubblesort so programmiert, dass immer nur unterschiedlich große Zahlen getauscht werden, so ist Bubblesort stabil.

Sortiert man ein und dieselbe Liste mit verschiedenen Verfahren, so stellt man sehr schnell fest, dass der Aufwand, den ein Algorithmus zum Sortieren betreiben muss die Geschwindigkeit erheblich beeinflusst. Um Verfahren genauer vergleichen zu können, kann man im Quellcode zwei Zähler einbauen:

1. Ein Zähler zählt jedes Ausführen einer Entscheidung bzw. eines Vergleichs. Da Vergleich zeitintensiv sind, ist dies ein Kriterium für die Geschwindigkeit der Verfahren.
2. Der zweite Zähler zählt die Anzahl der Tauschoperationen. Damit ist der Austausch zweier Elemente in der Liste, die wegen bestimmter Entscheidungen des Algorithmus die Plätze in der Liste tauschen sollen.

Die Wahl bestimmter Parameter beim Sortieren kann ebenfalls großen Einfluss auf die Geschwindkeit haben. Beispielsweise kann beim Quicksort-Algorithmus das Pivot-Element geschickt gewählt werden, sodass die Zahl der Tauschoperationen drastisch gesenkt wird.

Der Aufbau der Liste vor der Sortierung hat unter Umständen großen Einfluss auf die Dauer. Man unterscheidet in der Regel drei Fälle:

1. Best Case
2. Average Case
3. Worst Case