Time and Space Complexity

Zeitkomplexität:

• O(n + k)
  • wobei n die Anzahl der Elemente und k der Wertebereich (max + 1) ist. Ein Durchlauf zum Zählen, ein Durchlauf über die Zählwerte zum Wiederaufbau.
• Wenn k klein und fest ist, ist dies effektiv O(n), schneller als das O(n log n) von vergleichsbasierten Sortieralgorithmen.

Platzkomplexität:

• O(n + k)
  • Das Zähl-Array verwendet O(k) und die Ausgabe verwendet O(n).

Zusammenfassung:

• Counting Sort ist ein stabiler, nicht-vergleichsbasierter Sortieralgorithmus, der für kleine Ganzzahlbereiche in linearer Zeit läuft.
• Er ist ungeeignet, wenn der Wertebereich k sehr groß ist, da das Zähl-Array riesig wäre. Diese Version setzt nicht-negative Ganzzahlen voraus.