Adding elements to a sorted array?

Question

What would be the fastest way of doing this (from an algorithmic perspective, as well as a practical matter)?I was thinking something along the following lines.I could add to the end of an array and then use bubblesort as it has a best case (totally sorted array at start) that is close to this, and has linear running time (in the best case).On the other hand, if I know that I start out with a sorted array, I can use a binary search to find out the insertion point for a given element.My hunch is that the second way is nearly optimal, but curious to see what is out there.How can this best be done?

Answer 1

In terms of efficiency, the second option is definitely more optimal. It reduces the amount of work and calculations that your CPU has to endure and takes up less temporary memory. A Binary search would work great! This process is not too fancy so not much code needs to be done.

Answer 2

From the standpoint of simplicity, it would be best to do a simple linear scan of the sorted array and find the right position of the new element.

If you want to use binary search, it would be a modified algorithm and you may still end up doing a linear scan towards the end. So I would code it with the first method for the sake of simplicity and yes it would be O(n) algorithm