Zusammenfassung von Laufzeit und Platzbedarf

	Best	Average	Worst	zusätzlicher Platz
SelectionSort	$O( n^2 )$	$O( n^2 )$	$O( n^2 )$	$O(1)$
BubbleSort	$O(n)$	$O( n^2 )$	$O( n^2 )$	$O(1)$
MergeSort	$O(n \cdot log~n)$	$O(n \cdot log~n)$	$O(n \cdot log~n)$	$O(n)$
QuickSort	$O(n \cdot log~n)$	$O(n \cdot log~n)$	$O( n^2 )$	$O(log~n)$
HeapSort	$O(n \cdot log~n)$	$O(n \cdot log~n)$	$O(n \cdot log~n)$	$O(1)$

Der lineare zusätzliche Platzbedarf beim Mergesort-Algorithmus wird verursacht durch die Methode merge, welche für das Mischen zweier sortierter Folgen ein Hilfs-Array derselben Größe benötigt.

Der logarithmische zusätzliche Platzbedarf beim Quicksort-Algorithmus wird verursacht durch das Zwischenspeichern der Intervallgrenzen für die noch zu sortierenden Array-Abschnitte, die jeweils nach dem Aufteilen anhand des Pivot-Elements entstehen.

Beispiel:

Sei ein Array gegeben mit insgesamt 16 Daten. Der initiale Aufruf von Quicksort wird versorgt mit den Arraygrenzen [0,15]. Folgende Sequenz von gespeicherten Intervallgrenzen entsteht:

[0,15]
[0,7][8,15]
[0,7][8,11][12,15]
[0,7][8,11][12,13][14,15]
[0,7][8,11][12,13]
[0,7][8,11]
[0,7][8,9][10,11]
[0,7][8,9]
[0,7]
[0,3][4,7]
[0,3][4,5][6,7]
[0,3][4,5]
[0,1][2,3]
[0,1]

Die maximale Ausdehung liegt bei einer Folge von jeweils halbierten Intervallgrenzen; davon gibt es logarithmisch viele.