Ich hab mit binärer bzw. arithmetischer Suche in Listen hervorragende Erfahrungen gemacht, auch bei mehreren zigtausend Einträgen. Im Worst-Case bist du da mit einer Suchzeit von O(log(n)) unterwegs, und der WC tritt selten genug auf, bzw. je homogener die Liste, desto seltener.
Vorteil dabei ist zudem, dass eine Suche nach einem Eintrag im Falle des Nichtfindens auch gleich die Position liefert, an der einzufügen wäre um gleich während des Aufbaus die Sortierung zu gewährleisten, und Suchen+Einfügen damit im Grunde ein und die selbe Operation ist, die auch nur ein Mal pro Durchlauf gemacht werden muss.
Nach meinem Empfinden ist hier eine Hashtable fast schon Overkill, wenn auch nicht weniger Elegant. Aber ein Array der Länge Max(Cardinal) ist größtmöglicher Unfug
"When one person suffers from a delusion, it is called insanity. When a million people suffer from a delusion, it is called religion." (Richard Dawkins)