Time and Space Complexity

Zeitkomplexität:

• O(d * (n + k))
  • wobei n die Anzahl der Elemente ist, k die Basis (10) und d die Anzahl der Stellen im größten Wert. Jeder der d Durchläufe verrichtet O(n + k) Arbeit.
• Wenn d klein und fest ist, verhält sich dies wie O(n), schneller als das O(n log n) von Vergleichssortierungen.

Platzkomplexität:

• O(n + k)
  • Jeder Durchlauf erstellt ein Ausgabearray der Größe n und ein Zählarray der Größe k.

Zusammenfassung:

• Radix Sort ist ein stabiles, nicht-vergleichendes Sortierverfahren, das O(n log n) für Ganzzahlschlüssel mit einer begrenzten Anzahl von Stellen schlagen kann.
• Es benötigt Schlüssel, die in Stellen aufgeteilt werden können, sowie zusätzlichen Speicherplatz, und diese Version setzt nicht-negative Ganzzahlen voraus.