3
$\begingroup$

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
    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.2011-09-30
  • 0
    @Henning: In other words, you're ignoring the question.2011-09-30
  • 0
    @Tony, he asked me how I would sort the various lists, and I answered truthfully to the best of my ability.2011-09-30
  • 0
    @Henning: Well duh. In *other* other words, you're disparaging the question. So I just voted it up.2011-09-30

2 Answers 2