Sortieren ist eines der grundlegenden Probleme in der Informatik. Die Zeitkomplexität für vergleichsbasiertes Sortieren ist bekanntermaßen Theta(n log n). Wenn nun die Eingaben auf Integer beschränkt werden und eine RAM mit einer beschränkten und von der Eingabegröße abhängigen Wortlänge als Modell für die Komplexitätsanalyse gewählt wird, kann diese Schranke unterschritten werden. Die Beschränkung der Wortlänge ist notwendig um reale Einschränkungen abbilden zu können. Die Frage ob mit diesen Vorraussetzungen in linearer Zeit sortiert werden kann ist noch offen.
Der in der Arbeit vorgestellte Algorithmus von Han und Thorup kombiniert bekannte Algorithmen für die Sortierung von Integern mit einem neuen Algorithmus der eine Eingabemenge in kleinere Mengen auf denen eine gewisse Ordnung definiert ist aufteilt. Somit wird eine Komplexität von O(n sqrt(log log n)) für das randomisierte Sortieren beliebig langer Integer erreicht.