Sorting O(log n) elements in O(n) time

Question

I am presented with the following problem: In an array of $n$ sorted numbers and $f(n)$ unsorted numbers where $f(n)=O(\log n)$, find an algorithm to sort the entire array in $O(n)$ time.

What I am getting from this is that I should find an algorithm to sort $n + O(\log n)$ numbers in $O(n)$ time. I think the first step would be to sort the $O(\log n)$ numbers in $O(n)$ time. But the only sorting algorithm I have learned that can possibly be $O(n)$ is insertion sort, and that is only in the best case when all the numbers are already sorted. The $O(\log n)$ numbers part confuses me as well since $O(\log n)$ isn't an integer as far as I know but a function.

I really don't know where to begin on this, so I'd be very grateful for any and all advice. Thank you all!

Answer 1

Merging $n$ sorted numbers and $\text{log}\ n$ unsorted numbers asks you to do two things:

1. Sort the $\text{log}\ n$ unsorted numbers in $O(\text{log}\ n\ \text{log}\ \text{log}\ n)$.

2. Merge $n$ sorted numbers and $\text{log}\ n$ sorted numbers in $O(n + \text{log}\ n)$.

This yields the total time complexity of $O(n + \text{log}\ n + \text{log}\ n\ \text{log}\ \text{log}\ n)$ = $O(n)$.

Answer 2

If you use some primitive algorithm that sorts n items in O(n^2) then it sorts log n items in O(log^2 n), which is much faster than O(n).

Using quick sort, you can sort n items in O(n log n) and (n / log n) items n O(n). In practice, if n = 1,000,000 and log n = 20, you can merge 1,000,000 / 20 = 50,000 items in O(n), not just log n = 20.

O(n) is of course the best you can achieve if you need to insert even one item into your sorted array, because up to n existing elements need to be moved.