Wie erreicht ein Algorithmus, der verteilt, diese Verbesserung der Laufzeit und womit bezahlt er diese Verbesserung?

Question

Sortieren durch Verteilen erreicht eine bessere Laufzeitkomplexität als Sortieren durch Vergleichen. Wie erreicht ein Algorithmus, der verteilt, diese Verbesserung der Laufzeit und womit bezahlt er diese Verbesserung?

Answer 1

Ein Algorithmus, der verteilt, erreicht die Verbesserung der Laufzeit dadurch, das er den ungefähren Ort des einzusortierenden Elementes durch eine einmalige Berechnung ermittelt, anstatt ihn durch mehrere Vergleiche zu ermitteln.

Die Verbesserung wird dadurch bezahlt, dass die Länge des Schlüssels begrenzt ist.