Inserting a number into a sorted array!

Question

I would like to write a piece of code for inserting a number into a sorted array at the appropriate position (i.e. the array should still remain sorted after insertion)

My data structure doesn't allow duplicates.

I am planning to do something like this:

1. Find the right index where I should be putting this element using binary search
2. Create space for this element, by moving all the elements from that index down.
3. Put this element there.

Is there any other better way?

Answer 1

If you really have an array and not a better data structure, that's optimal. If you're flexible on the implementation, take a look at AA Trees - They're rather fast and easy to implement. Obviously, takes more space than array, and it's not worth it if the number of elements is not big enough to notice the slowness of the blit as compared to pointer magic.

Answer 2

A heap based implementation of a tree would be more efficient if you are inserting a lot of elements - log n for both locating/removing and inserting operations.

Answer 3

Does the data have to be sorted completely all the time? If it is not, if it is only necessary to access the smallest or highest element quickly, Binary Heap gives constant access time and logn addition and deletion time. More over it can satisfy your condition that the memory should be consecutive, since you can implement a BinaryHeap on top of an array (I.e; array[2n+1] left child, array[2n+2] right child).