Assume a sorted list of $n$ elements followed by $f(n)$ elements in random order.

How would you sort the whole list given the following:

a) $f(n)=O(1)$

b) $f(n)=O(\log n)$

c) $f(n)=O(n^{1/2})$

d) How big can $f(n)$ be for the list to remain sortable in $O(n)$ time?

I hope somebody can help, thanks in advance.

  • 2
    $\begingroup$ Unless this was postively known to be a performance bottleneck, I would just throw the default library quicksort implementation at it and not worry further. $\endgroup$ – Henning Makholm Sep 30 '11 at 18:23
  • $\begingroup$ @Henning: In other words, you're ignoring the question. $\endgroup$ – TonyK Sep 30 '11 at 20:24
  • $\begingroup$ @Tony, he asked me how I would sort the various lists, and I answered truthfully to the best of my ability. $\endgroup$ – Henning Makholm Sep 30 '11 at 21:05
  • $\begingroup$ @Henning: Well duh. In other other words, you're disparaging the question. So I just voted it up. $\endgroup$ – TonyK Sep 30 '11 at 21:07

You can sort the unordered elements in time $O(f(n) \log f(n))$, and then merge the two lists in time $O(\max (n, f(n)))$. So this gives you $O(n)$ as long as $f(n) \log f(n) = O(n)$, which I think answers d).

The trouble with a) is this: With a binary search, you can find the positions to insert the unordered elements in $O(\log n)$ time; but physically inserting them in the list takes $O(n)$ time, because you have to shift all those elements up by one. The same applies, mutatis mutandis, to b) and c).


I am assuming f(n) is the number of unordered elements in the list. I don't understand the significance of O of f(n), so maybe I don't understand the problem.

You can sort the unordered elements separately using a sort O(f(n) log f(n)) and then merge them with the ordered elements in an O(n) operation. In order to sort the entire list in O(n) time, I believe the unordered list would have to be already sorted, so f(n) would have to be 0 or 1.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.