How to insert an element in a sorted array so the the array remains sorted?

Question

In c++, std::set which stores its element in sorted order can insert elements in O(log n) time. But all the methods i know take linear time:

Inserting the element at the end of the array and swapping it with the previous element until the previous element is less than it- takes linear time.

Using binary search on the array and finding the position the position of the element to be inserted: takes O(log n) time but inserting the element to the given position takes O(n) time in the worst case.

If we use the sorted array as heaps, we can insert an element in O(log n) time but even if the array remains a heap after that, there is no guarantee that it remains sorted.

I need a method to insert an element in a sorted array in O(log n) time, and i know this is possible because std::set can do it, but i dont know how.

Answer 1

The solution is to use a different data-structure. std::set has for instance been implemented using a red-black-tree.

In general, you cannot do this with plain arrays.