Ich habe eine Liste, und die soll bitte immer sortiert sein

[Namenloser]

Man sollte aber beachtet, dass das Einfügen dabei auf jeden Fall O(n) Zeit kostet.

Wenn man eine verkettete Liste verwendet, muss man durchschnittlich die Hälfte aller Items durchlaufen, bis man die richtige Einfügestelle findet, dafür geht das Einfügen dann schnell. Verwendet man stattdessen ein Array (wie TList), kann man zwar eine binäre Suche durchführen, aber dafür muss man dann beim Einfügen O(n) Items an eine andere Stelle verschieben, also auch nicht besser.

Die einzige wirklich saubere Variante für eine sortierte Liste ist ein balancierter Baum. Dort geht das Einfügen in O(log n). Ich glaube, Delphi hat von Haus aus aber leider keine Implementierung. Ich hab mal eine geschrieben, aber sie ist nicht sauber genug, um sie hier zu veröffentlichen...

Wenn man keinen Baum zur Verfügung hat, dann ist es schlauer, alle Items erst mal unsortiert einzufügen, und dann am Ende in O(n log n) zu sortieren.

Edit: Wobei mir einfällt, Heaps gibt es auch noch. Sind leichter zu implementieren als Bäume und das Einfügen geht auch in O(log n). Dafür kann man aber immer nur das „größte“ oder „kleinste“ (je nachdem) Item auslesen. Aber für eine Priority-Queue könnte das ja z.B. schon reichen.