You want to use a vector, and a bsearch-based insertion sort for this, so that the vector is always kept sorted. I wrote such code in C++ for a commercial application development framework (SDK) years ago (in the 1990's). Based upon the bsearch (binary search) algorithm, it would find the proper spot to insert the item, and then move the elements below down and stick the new one in that spot. It would detect if the array needed to be resized, and do that automatically. At that time, the STL collection classes were still a dream, or I would have used a std::vector instead of rolling my own. It handles the resizing and insertion stuff quite nicely, pushing the data down and resizing as needed. That would have saved me a couple of days coding effort! :-)
An additional tidbit - I also did head/tail optimizations for large arrays. Since we were dealing with collections of up to 100,000+ elements, that made a huge performance improvement, especially when dealing with inserting already sorted data, such as from a database query that utilized an "order by" clause.