Sortieralgorithmen verstehen: Bubble Sort, Merge Sort und Quicksort

Fast jede Anwendung muss irgendwann Daten sortieren: eine Liste von Namen alphabetisch, Produkte nach Preis oder Suchergebnisse nach Relevanz. Natürlich hat jede Sprache dafür eine eingebaute Funktion – in Python sorted(), in JavaScript .sort(). Trotzdem lohnt es sich, zu verstehen, wie diese Funktionen intern arbeiten. Sortieralgorithmen sind ein perfektes Übungsfeld, um ein Gefühl für Laufzeit, Rekursion und algorithmisches Denken zu bekommen. In diesem Beitrag lernst du drei klassische Verfahren kennen und verstehst, warum manche davon dramatisch schneller sind als andere.

Warum überhaupt selbst sortieren?

Wenn es sorted() schon gibt, warum sich mit eigenen Algorithmen beschäftigen? Weil du dabei ein zentrales Konzept lernst: die Zeitkomplexität. Ein Algorithmus, der bei 10 Elementen schnell wirkt, kann bei 10 Millionen Elementen unbrauchbar langsam sein. Sortieren zeigt diesen Unterschied besonders anschaulich, weil die Verfahren von sehr langsam (O(n²)) bis effizient (O(n log n)) reichen.

Zur Erinnerung: Die Big-O-Notation beschreibt, wie stark der Aufwand mit der Eingabegröße n wächst. Bei O(n²) vervierfacht sich die Arbeit, wenn sich die Datenmenge verdoppelt. Bei O(n log n) wächst sie nur wenig mehr als linear – ein riesiger Unterschied bei großen Datenmengen.

Bubble Sort: einfach, aber langsam

Bubble Sort ist der Einsteiger-Algorithmus schlechthin. Die Idee: Du gehst wiederholt durch die Liste, vergleichst jeweils zwei benachbarte Elemente und vertauschst sie, wenn sie in der falschen Reihenfolge stehen. Große Werte „blubbern" so nach und nach ans Ende – daher der Name.

def bubble_sort(zahlen):
    liste = zahlen.copy()
    n = len(liste)
    for i in range(n):
        getauscht = False
        # Nach jedem Durchlauf steht das größte Element hinten
        for j in range(0, n - i - 1):
            if liste[j] > liste[j + 1]:
                liste[j], liste[j + 1] = liste[j + 1], liste[j]
                getauscht = True
        # Wenn nichts getauscht wurde, ist die Liste sortiert
        if not getauscht:
            break
    return liste

print(bubble_sort([5, 2, 9, 1, 5, 6]))
# [1, 2, 5, 5, 6, 9]

Die Optimierung mit getauscht sorgt dafür, dass wir abbrechen, sobald die Liste sortiert ist. Trotzdem bleibt die Laufzeit im schlechtesten Fall bei O(n²), weil wir für jedes Element potenziell die ganze restliche Liste durchlaufen. Für den Alltag ist Bubble Sort zu langsam – als Lernbeispiel aber ideal.

Merge Sort: teile und herrsche

Merge Sort ist deutlich schneller und arbeitet nach dem Prinzip Divide and Conquer (teile und herrsche). Die Liste wird immer weiter halbiert, bis nur noch einzelne Elemente übrig sind. Diese werden dann paarweise wieder sortiert zusammengeführt (englisch merge).

def merge_sort(liste):
    if len(liste) <= 1:
        return liste

    mitte = len(liste) // 2
    links = merge_sort(liste[:mitte])
    rechts = merge_sort(liste[mitte:])
    return merge(links, rechts)


def merge(links, rechts):
    ergebnis = []
    i = j = 0
    while i < len(links) and j < len(rechts):
        if links[i] <= rechts[j]:
            ergebnis.append(links[i])
            i += 1
        else:
            ergebnis.append(rechts[j])
            j += 1
    # Rest anhängen
    ergebnis.extend(links[i:])
    ergebnis.extend(rechts[j:])
    return ergebnis

print(merge_sort([38, 27, 43, 3, 9, 82, 10]))
# [3, 9, 10, 27, 38, 43, 82]

Der Trick steckt in der Funktion merge: Da beide Teillisten bereits sortiert sind, reicht ein einziger Durchlauf, um sie korrekt zu verschmelzen. Das Halbieren erzeugt etwa log n Ebenen, und jede Ebene braucht O(n) Arbeit – zusammen ergibt das eine zuverlässige Laufzeit von O(n log n), auch im schlechtesten Fall.

Quicksort: schnell durch geschicktes Pivot

Quicksort ist in der Praxis oft der schnellste vergleichsbasierte Algorithmus und arbeitet ebenfalls nach dem Teile-und-herrsche-Prinzip. Man wählt ein Pivot-Element und teilt die Liste in drei Gruppen: alles Kleinere, alles Gleiche und alles Größere. Anschließend werden die Teile rekursiv sortiert.

def quicksort(liste):
    if len(liste) <= 1:
        return liste

    pivot = liste[len(liste) // 2]
    kleiner = [x for x in liste if x < pivot]
    gleich = [x for x in liste if x == pivot]
    groesser = [x for x in liste if x > pivot]

    return quicksort(kleiner) + gleich + quicksort(groesser)

print(quicksort([10, 7, 8, 9, 1, 5]))
# [1, 5, 7, 8, 9, 10]

Diese Variante ist besonders gut lesbar, weil sie mit List Comprehensions arbeitet. Im Durchschnitt erreicht Quicksort O(n log n). Im schlechtesten Fall – etwa bei einer bereits sortierten Liste und schlechter Pivot-Wahl – kann er auf O(n²) abrutschen. In der Praxis wird das Pivot deshalb oft zufällig oder als Median gewählt.

Vergleich und Praxis

Fassen wir die wichtigsten Eigenschaften zusammen:

• Bubble Sort: O(n²), sehr einfach, nur für Lernzwecke oder winzige Listen.
• Merge Sort: O(n log n) garantiert, stabil (gleiche Werte behalten ihre Reihenfolge), braucht aber zusätzlichen Speicher.
• Quicksort: im Schnitt O(n log n), sortiert in der klassischen Variante speichersparend „in place", ist aber nicht stabil.

Im echten Code solltest du fast immer die eingebaute Funktion nutzen – sie ist hochoptimiert und getestet. Pythons sorted() verwendet intern übrigens Timsort, eine clevere Mischung aus Merge Sort und Insertion Sort:

daten = [5, 2, 9, 1, 5, 6]

# Aufsteigend
print(sorted(daten))          # [1, 2, 5, 5, 6, 9]

# Absteigend
print(sorted(daten, reverse=True))  # [9, 6, 5, 5, 2, 1]

# Nach eigenem Kriterium, z. B. Wortlänge
woerter = ["Banane", "Kiwi", "Apfel"]
print(sorted(woerter, key=len))  # ['Kiwi', 'Apfel', 'Banane']

Fazit

Sortieralgorithmen sind mehr als nur akademische Übungen: Sie machen abstrakte Konzepte wie Rekursion, Divide and Conquer und Zeitkomplexität greifbar. Bubble Sort zeigt dir das Grundprinzip, Merge Sort und Quicksort demonstrieren, wie ein cleverer Ansatz die Laufzeit von O(n²) auf O(n log n) drückt. Im Alltag greifst du zu sorted() – aber wenn du verstehst, was darunter passiert, triffst du bessere Entscheidungen über Performance und kannst technische Fragen souverän beantworten. Nimm dir am besten die Beispiele, füg ein paar print-Ausgaben in die Schleifen ein und beobachte Schritt für Schritt, wie sich die Listen sortieren.