Best sort method for median: median heap or insertion sort on a vector

Question

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?

Answer 1

You are asking many questions, and I will only answer two of them. If you have a sorted vector of length $n$ followed by $m$ unsorted elements, the best way to sort the entire vector is to use an $O(m\log m)$ sorting algorithm on the tail, and then merge the two sorted lists in $O(n+m)$. The total running time is $O(n+m\log m)$, which is $O(n)$ if $m = O(n/\log n)$. If $m = \omega(n/\log n)$ then the problem is more complicated; asymptotically optimal bounds are known in the decision tree model, but I'm not sure they can be implemented efficiently enough (see for example Kahn ad Kim, Entropy and Sorting).

Another question, which you haven't actually asked, is about lower bounds. Suppose that you have a data structure in which insert takes (amortized) time $\alpha(n)$ and median takes (amortized) time $\beta(n)$, where $n$ is the number of elements in the structure. Suppose further that $\alpha(O(n)) = O(\alpha(n))$ and $\beta(O(n)) = O(\beta(n))$, and that $\alpha,\beta$ are monotone (this is the case for functions of the type $\Theta(n^s\log^t n)$). Then $\alpha(n) + \beta(n) = \Omega(\log n)$, assuming the operations are implemented using the comparison model (two datums can be compared, but are otherwise completely opaque).

For the proof, here is how to sort a list of length $n$. First insert the list. Then, extract the median, add $-\infty$ (or the minimum value) twice, and repeat. You recover the sorted lower half of the list. Now add enough copies of $+\infty$ (or the maximum value), and recover similarly the upper half of the list. This requires at most $O(n\alpha(O(n)) + n\beta(O(n))) = O(n(\alpha(n)+\beta(n)))$. In the comparison model, there is a lower bound of $\Omega(n\log n)$, so $\alpha(n) + \beta(n) = \Omega(\log n)$.