Ein etwas komplexeres Sortierverfahren, das wir Ihnen hier vorstellen möchten, heißt Bubblesort. Mit dem Sortierverfahren Bubblesort möchten wir eine unsortierte Liste von Zahlen aufsteigend sortieren. Wir fangen mit der ersten Zahl an und vergleichen diese mit ihrem rechten Nachbarn. Ist der rechte Nachbar größer, so belassen wir diese Reihenfolge. Ist er kleiner, so tauschen wir die beiden Zahlen. Nun gehen wir zur nächsten (zweiten) Zahl weiter, vergleichen auch diese wieder mit ihrem rechten Nachbarn, und tauschen die beiden Zahlen, falls nötig. So gehen wir schrittweise die Liste durch bis wir bei den letzten beiden Zahlen sind. Dann wiederholen wir diesen Listendurchlauf auf die gleiche Weise, und zwar so oft, bis alle Zahlen aufsteigend sortiert sind.

In der theoretischen Informatik versuchen wir Algorithmen danach einzuschätzen, wie sich deren Verhalten ändert, wenn sich die Menge der Daten ändert. Je länger die Liste der zu sortierenden Zahlen ist, desto mehr Zeit benötigt offensichtlich das Verfahren. Legen wir fest, dass die Länge der zu sortierenden Zahlen n sei, hier im Beispiel ist also n=5. Weiterhin sei m die Anzahl der Vergleiche zwischen zwei Zahlen, die im Laufe der Ausführung des Verfahrens durchgeführt werden. Wie hängen n und m für Bubblesort zusammen? Es geht hier nicht um eine exakte Formel, sondern um die Abschätzung der Größenordnung, wie n und m zusammenhängen.