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.