# Can you insert into sorted list with time O(1)?

Wondering if this was possible. If I have a sorted list, can I find the right spot for an integer and insert it, all in O(1) time? The only way I can think to do this is via having a MASSIVE hashmap with one slot for each possible integer. 2 billion different integers * 4 bytes per integer = 8 gigabytes....but it'd technically work. There has to be a better way to do this though, right?

Sounds like you want a solution for bounded integers, 32-bit for example. If so, any sorted dictionary whose complexity depends on the key length only will do what you want. Two examples are binary trie and van Emde Boas tree.

One way to convince yourself it is not possible is to consider what it would enable. Assume there exists an O(1) algorithm for insertion into an unbounded sorted array, CONST_INSERT. Then we can define a O(n) sorting algorithm as follows:

• Let $$L$$ be an empty list $$()$$ and $$U = (u_1, u_2, \ldots u_n)$$ be an unsorted list.
• Iterate over $$i: 1 \rightarrow n$$, inserting $$u_i$$ into $$L$$ using CONST_INSERT

This produces a sorted array, since at the end of every iteration $$i$$, $$L$$ will be exactly a sorted list of $$(u_1 \ldots u_i)$$. And it will have a runtime of O(n).

From a practical perspective, if an O(n) sorting algorithm existed it would be very useful, so you'd likely know about it. From a theory perspective, resources like this might help you convince yourself that no such sorting algorithm could exist.

• OP specifically mentioned that sorting is done for 4-byte integers. Comparison-based sorting lower bound doesn’t apply here. – Dmitri Urbanowicz Sep 1 at 16:04
• That's a good point, and it looks like your answer is a good overview of the things applicable to the bounded case. – Keon Sep 4 at 21:57

One thing before I explain: HashMap doesn't use an array that big, it uses chaining, which is another concept you'll have to look up. And if you're talking about creating an array size 2 billion, that still won't work because you still have to scan the 2 billion entries in the array. Ok, technically that's O(1), but only because O(2 billion) is counted as O(1).

I actually wondered about this for a long time. If you think about it, there is no possible way even with the HashMap. Before I get into why HashMap doesn't work, if you don't use a HashMap, you'll have to scan the whole size that you have to insert. Now to the HashMap part, after inserting you're number, you'll have to update every entry after that. And if you don't, you'll get an O(1) insertion once, but after that you'll get wrong insertions.