RadixSort sortiert n m-Ziffern-lange Zahlen in einer Laufzeit von O(m*n). Es kann davon ausgegangen werden das m deutlich kleiner ist als n, dh. wir viele Zahlen haben, die eine relativ dazu kleine Länge haben.

RadixSort sortiert die Zahlen schrittweise von vorn nach hinten. Dh. zuerst werden die Zahlen nach der ersten Stelle sortiert, dann in den jeweiligen Teilbereichen nach der zweiten. Das Problem hier besteht darin, dass viele Zeiger auf die Grenzen der Teilbereiche gespeichert werden müssen.

Um nicht mehr so viele Zeiger auf die Grenzen der Teilbereiche speichern zu müssen, gibt es die Verbesserung des RadixSort, die von hinten nach vorn sortiert. Dh. zuerst werden alle Zahlen nach der letzten Stelle sortiert, dann nach der vorletzten. Die Sortierung durch eine vorhergehende Sortierung soll dabei aufrecht erhalten bleiben. Eine Möglichkeit zur Implementation der Sortierung nach den einzelnen Zahlen ist CountingSort.