Welcher Sortieralgorithmus hat im Worst Case eine Zeitkomplexität von O(n^2), ist aber im Average Case mit O(n log n) einer der schnellsten Sortieralgorithmen in der Praxis?

Quick Sort hat im Average Case eine Zeitkomplexität von O(n log n) und ist in der Praxis oft der schnellste Sortieralgorithmus. Im Worst Case (z.B. bei bereits sortierter Eingabe und schlechter Pivotwahl) degeneriert er jedoch zu O(n^2). Merge Sort hingegen hat immer O(n log n), benötigt aber zusätzlichen Speicher.