I'm trying to decide between two methods of calculating a median, that will optimize the following operations:
- Add integer to data structure (insert)
- Get the median of all integer (getMedian)
The program will add a random number of integers (no limit on how many, but generally going to be relatively small amount) to the data structure before trying to access the median, and then repeat this process an indefinite amount of times.
With the median heap method, insert will take O(log(n)) on average and getMedian will be O(1).
What I'm wondering is what would happen if instead I simply used a vector. Insert would be amortized O(1). Then when getMedian is called, the vector is sorted with insertion sort, followed by simply accessing the middle element, O(1).
Would this be faster in the long run? There will almost always be more calls to insert than getMedian in the program, but I'm not sure if the insertion sort will be faster. I believe it is a relatively fast sort, O(n), on a partially sorted array, but I'm not sure.
For instance, if I had a vector with 100 million integers that were sorted followed by 4 unsorted elements, would insertion sort be O(n)? What if I had 50 million unsorted elements (very unlikely in the program, but possible)? And at how many unsorted elements would it be better to use another sort, like quicksort?