Someone on HN mentioned the 'magic of ____ arrays' or something like that where search, insertion, merge, etc. were all constant time operations...

Ah! Clojure's persistent vectors: https://hypirion.com/musings/understanding-persistent-vector...

I would use stacks to sort. The book was about 1000 pages? I'll do about 10 stacks. Then figuring out which stack to put a given page in is fast. (Abstract this and you wind up with a binary tree, which is what made me think of the persistent vectors above.)