Given a sorted array of n elements, sort a subset n/2 elements in linear time

Question

I have a sorted array of n elements. Now I am given n/2 elements each of which belong to the sorted array. The n/2 elements are taken at random from the sorted array. How to sort these n/2 elements in linear time?

Answer 1

One approach involves hashing. Build a hash set that contains all n / 2 elements drawn from the array. If duplicates are allowed, instead build a hash table from elements to their frequencies. This will take O(n) time, on expectation.

Then, iterate across the sorted array in ascending order and, for each element of the array, check if it's in the hash set / hash table. If so, append that element to the output array (and, if duplicates are allowed, do so once per copy of the element in the set). This will take O(1) time, on expectation, per element of the array, and therefore this step takes time O(n) as well.

Therefore, the total runtime is O(n), on expectation.

Hope this helps!