Beim Problem des Online-Sortierens erscheinen n Elemente der Reihe nach und müssen jeweils unmittelbar und unwiderruflich in eine freie Zelle eines Arrays eingefügt werden. Das Ziel besteht darin, die Gesamtsumme der absoluten Differenzen zwischen benachbarten Array-Einträgen zu minimieren. Dieses Problem wurde von Aamand, Abrahamsen, Beretta und Kleist (2023) als technisches Hilfsproblem zur Analyse geometrischer Packing-Probleme eingeführt.

Während unter adversarialen Eingabesequenzen eine Schranke von Θ(√n) gilt, erlaubt die stochastische Variante mit i.i.d. Eingaben aus U(0,1) deutlich bessere Kosten, wie Abrahamsen, Bercea, Beretta, Klausen und Kozma (2024) zeigen.

Aufbauend auf ihrem Algorithmus, der w.h.p. Kosten von Õ(n^1/4) erreicht, und unter Einbeziehung des polylogarithmischen Algorithmus von Fotakis, Kalavas, Platanos und Tolias (2025), entwerfen wir einen neuen adaptiven Algorithmus, den AdaptiveOnlineSorter (AOS). Dieser partitioniert das Array schrittweise und passt Kapazitäten dynamisch an, um Ungleichgewichte auszugleichen. Er kombiniert diese Strukturierung mit heuristischen Platzierungsregeln, um lokale Kosten zu reduzieren.

Wir präsentieren eine Analyseskizze, die nahelegt, dass AOS ebenfalls polylogarithmische Kosten erreicht und damit in derselben Größenordnung wie der Algorithmus von Fotakis et al. liegt.

Ergänzend implementieren wir Varianten aller drei Algorithmen und vergleichen ihre empirischen Kosten mit einer einfachen Einfügeheuristik. Unsere Resultate zeigen, dass AOS unter Eingaben ≤ 700 000 ähnlich gute oder bessere Kosten als die anderen Algorithmen erzielt, allerdings um den Preis längerer Laufzeiten. Die Arbeit verdeutlicht damit, dass adaptive Strategien einerseits ein vielversprechender Ansatz für stochastisches Online-Sortieren sind, zugleich aber offene Fragen nach ihrer praktischen Vorteilhaftigkeit gegenüber einfachen Heuristiken aufwerfen.