Linear sorting using additional data structure (O(1) to find median of set, O(1) for adding element)

Question

Suppose we have arbitrary elements (we can compare them in O(1)) in array and magic DS in which we can add element in O(1) and find the median of elements in DS in O(1). We can't remove elements from DS and there are no equal elements in array. Also, we can create as many such DS as we need.

The question: is there a way to sort the array in O(n) using this DS?

Answer 1

Yes, if this data structure exists then it can be used to sort in O(n) time.

1. Scan the array to find the minimum and maximum elements. Call this min and max.
2. Insert all of the array elements into the data structure, in any order.
3. Insert n - 1 copies of min - 1. The median is now the smallest element from the original array.
4. Repeat n - 1 times:
   • Insert two copies of max + 1.
   • Read off the median, which will now be the next element from the original array in ascending order.

This procedure takes O(n) time, because

1. Finding the min and max is O(n),
2. Inserting n elements is n * O(1) = O(n),
3. Inserting n-1 elments is (n - 1) * O(1) = O(n),
4. Inserting two elements and reading the median is O(1), so doing this n - 1 times is O(n).