Erlang's ordsets() module has O(N) insertion. Since there's theoretical disagreement, here's experimental verification:

  11> f(), Ord_bench = fun(N) -> Random = [random:uniform(N) || _ <- lists:seq(1,N)], F = fun(Item, Set) -> ordsets:add_element(Item, Set) end, lists:foldl(F, ordsets:new(), Random) end.

#Fun<erl_eval.6.99386804> 12> timer:tc(fun() -> Ord_bench(10000) end). {337691, [1,2,3,4,5,7,8,10,12,13,14,15,16,17,18,19,21,23,24,26,27,28, 29,36,39,40,42|...]} 13> timer:tc(fun() -> Ord_bench(100000) end). {37167977, [1,2,3,5,7,9,10,11,12,15,16,17,18,19,20,21,23,24,25,26,27, 29,30,33,34,35,38|...]}

So, 337 ms turns into 37 seconds, roughly 100 times slower, when I increase the data size tenfold, which is what you'd expect from O(N) insertion.

Repeating for gb_sets, the results are 49 ms versus 484 ms.

Could the misunderstanding be that you don't realise that the ordsets module specifically guarantees that the representation is an ordinary sorted list?

(I am aware of e.g. skip lists. But that is not the same Erlang data structure as a sorted list.)

No, the misunderstanding is that I was thinking of Ordsets in Rust [1], which are implemented as trees.

[1] https://docs.rs/im/10.0.0/im/#sets

I would probably use the word array if you can access any item without traversal. Just a thought.