In fact inserting by bsearch is O(log N) when you keep a sorted array.