Komplexität

Untersucht wird hier das Verhältnis der Anzahl vor allem der Vergleichs und Umstelloperationen zur Anzahl der zu sortierenden Daten.

C(n) bedeutet Anzahl der Schlüsselvergleiche,
M(n) bedeutet Anzahl der Elemente-Umstellungen,
O(n) die Ordnung; so sind die Komplexitäten von C(n) oder/und M(n) von der Ordnung. Bei höheren Sortierverfahren ist die Komplexität günstiger.