# Introsort visualisieren: Quick Sort mit Heap-Fallback

> Introsort interaktiv: Quick Sort, der bei zu tiefer Rekursion zu Heap Sort wechselt und kleine Bereiche mit Insertion Sort sortiert. Garantiert O(n log n).

Adresse: https://marckimmel.de/informatik/sortieralgorithmen/intro-sort
English version: https://marckimmel.de/en/informatik/sortieralgorithmen/intro-sort.md

Quick Sort mit Tiefen-Limit, fällt bei zu tiefer Rekursion auf Heap Sort zurück.

Introsort (Introspective Sort) löst das pathologische Worst-Case-Verhalten von Quick Sort, das bei ungünstiger Pivot-Wahl in eine O(n²)-Laufzeit fallen kann. Der Algorithmus startet mit klassischem Quick Sort, beobachtet aber die Rekursionstiefe. Sobald diese das Limit von 2 · ⌊log₂(n)⌋ überschreitet, schaltet er auf Heap Sort um, der garantiert in O(n log n) bleibt. Sehr kleine Teilbereiche (typisch ≤ 16 Elemente) sortiert er mit Insertion Sort, weil dieser auf kleinen Eingaben sehr schnell ist. Damit hat Introsort die Average-Case-Schnelligkeit von Quick Sort, den garantierten O(n log n) Worst Case von Heap Sort und die Konstanten-Vorteile von Insertion Sort auf kleinen Bereichen. Der Speicherbedarf ist O(log n) für den Rekursions-Stack, und der Algorithmus ist nicht stabil.

Standard-Sortier-Algorithmus in der C++-STL (std::sort) seit dem C++11-Standard. Erste Wahl, wenn ein generischer, schneller in-place Sortier-Algorithmus mit garantierter O(n log n) Worst-Case-Laufzeit benötigt wird.

## Weiter

- [Sortieralgorithmen](https://marckimmel.de/informatik/sortieralgorithmen.md)