I am surprised that this works with a list. An array list would require moving data to insert at the right place, and a linked list would make it uneasy to get to the nth element in O(1).
Erlang's list are immutable cons cells (same idea as in LISP). This cons cell is just the element plus the "tail" pointer to the rest of the list. It is written as [H | T]. The last cons cell's tail is an empty list. So a list L = [1,2] is also the same as [1 | [2]] or [1 | [2 | []].
Underneath it is implemented like a linked list with nodes pointing to an element and then a pointer to the next. But explicit pointer manipulation, breaking and stitching lists together like one would do in C is not allowed. So it is all about traversing the list then inserting at the right place.
The reason ordsets are implemented using just lists is for simplicity and because they are designed for a small collections. Say maybe keeping some preferences around, or a list of options. Not storing 1M entries.
But there are other data structures and facilities to handle larger collections like gb_trees which are implemented as AVL trees. Another is an in-memory table called ETS. This one can be shared between processes (though terms are actually copied in most cases when reading and writing to/from it).
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.)
