Welk sorteeralgoritme heeft ook in het slechtste geval tijdcomplexiteit O(n log n) en sorteert met nauwelijks extra geheugen, zoals een werkarray?

Antwoord: B. Heapsort

Heapsort bouwt een binaire heap in de array zelf op, verwisselt herhaaldelijk het maximum in de wortel met het laatste element en maakt de heap kleiner. Daardoor kost het ook in het slechtste geval O(n log n) en is er maar een constante hoeveelheid extra geheugen nodig. Mergesort is in het slechtste geval ook O(n log n), maar heeft op een array een werkgebied nodig dat evenredig is met n. Quicksort is gemiddeld O(n log n) en in de praktijk snel, maar kan afhankelijk van de keuze van de pivot en de gegevens O(n²) worden. Merk op dat heapsort elementen vergelijkt die ver uit elkaar liggen, waardoor het cachegebruik inefficiënt is, en dat het niet stabiel is.