Die lineare Suche prüft die Elemente der Reihe nach und braucht im schlechtesten Fall $n$ Vergleiche. Sie funktioniert in jeder Liste. Die binäre Suche verlangt eine sortierte Liste. Sie vergleicht mit dem mittleren Element und sucht nur in der Hälfte weiter, in der das Gesuchte liegen kann.

Jeder Durchlauf halbiert den Suchbereich: Aus $n$ Elementen werden höchstens $n/2$, dann $n/4$ und so weiter. Für $n = 1000$ genügen 10 Durchläufe, für $n = 1000000$ sind es 20.

Alle Verfahren sortieren aufsteigend.

• Bubblesort vertauscht benachbarte Elemente, die falsch herum stehen, und schiebt so das größte nach hinten.
• Selectionsort sucht im unsortierten Teil das kleinste Element und tauscht es an den Anfang dieses Teils.
• Insertionsort fügt das nächste Element des unsortierten Teils an der richtigen Stelle in den sortierten Teil davor ein, wie Spielkarten auf der Hand.
• Mergesort teilt die Liste in zwei Hälften, sortiert jede Hälfte nach demselben Verfahren und mischt die beiden sortierten Hälften zu einer sortierten Liste.
• Quicksort wählt ein Pivot-Element, ordnet die kleineren Elemente links und die größeren rechts davon an und sortiert beide Seiten nach demselben Verfahren.

Bei Mergesort und Quicksort wendet sich das Verfahren auf kleinere Teillisten selbst an. Dieses Prinzip heißt Rekursion und kommt in der nächsten Lektion.

Ein Verfahren ist stabil, wenn Elemente mit gleichem Schlüssel ihre Reihenfolge behalten. Das zählt beim Sortieren nach mehreren Merkmalen: Wer erst nach Name und dann stabil nach Klasse sortiert, erhält die Namen innerhalb jeder Klasse alphabetisch. Selectionsort ist nicht stabil: Aus 2a, 2b, 1 wird 1, 2b, 2a.

Die Laufzeit $T(n)$ zählt die Grundschritte (etwa Vergleiche) in Abhängigkeit von der Größe $n$ der Eingabe, nicht Sekunden. Sie hängt auch von der Eingabe ab: Man unterscheidet besten, mittleren und schlechtesten Fall. Für große $n$ zählt nur die Wachstumsart. Die O-Notation gibt eine obere Schranke an: $T \in O(f)$ heißt, dass es eine Konstante $c > 0$ und ein $n_0$ gibt, sodass $T(n)$ für alle $n \geq n_0$ höchstens $c \cdot f(n)$ beträgt. Konstante Faktoren und kleinere Summanden fallen weg.

Verfahren teilt man nach der Wachstumsart ihrer Laufzeit in Komplexitätsklassen ein: $O(1)$ konstant, $O(\log n)$ logarithmisch, $O(n)$ linear, $O(n \log n)$, $O(n^2)$ quadratisch und $O(2^n)$ exponentiell. Der Logarithmus hat hier die Basis 2. Eine andere Basis ändert nur den konstanten Faktor.

Angenommen, ein Rechner schafft eine Milliarde Schritte pro Sekunde. Bei einer Million Elementen braucht ein Verfahren mit $n \log_2 n$ Schritten etwa 0,02 Sekunden, eines mit $n^2$ Schritten 1000 Sekunden, fast 17 Minuten. Bei $2^n$ Schritten und $n = 100$ dauert es länger, als das Weltall alt ist.

Ein Sortierverfahren ist korrekt, wenn es für jede Eingabe terminiert und die Ausgabe aufsteigend geordnet und eine Umordnung der Eingabe ist. Man begründet das mit einer Schleifeninvariante, einer Aussage, die vor und nach jedem Durchlauf gilt. Beim Insertionsort lautet sie: Nach dem Durchlauf für Index $i$ sind die vorderen $i + 1$ Elemente sortiert. Am Ende der Schleife folgt daraus die Korrektheit.

Effizienz meint Laufzeit und Speicherbedarf. Ein Verfahren mit nur konstantem Zusatzspeicher arbeitet am Platz. Jedes Verfahren, das nur durch Vergleiche sortiert, braucht im schlechtesten Fall mindestens etwa $n \log_2 n$ Vergleiche.

Mergesort ist auch im schlechtesten Fall schnell, braucht dafür aber Zusatzspeicher. Beim Quicksort tritt der schlechteste Fall ein, wenn das Pivot immer das kleinste Element ist.