You wouldn't actually have to sort everything again when a new item is added.

Using the same Half-split idea, you can quickly find the point where the new record should be inserted. Then just move everything after it, down one location. Not sure how long the move would take though.

That way the lookup will be quick.

Just a thought.
<br>