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

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!

• Do you know merge sort?
– holf
Commented Oct 17, 2023 at 1:28
• I do know mergesort, but that would be Θ(n lg n) time and the problem is asking for exactly O(n). If I sort the unsorted section in Θ(n lg n) time, merge it with the sorted array, and then sort that array in Θ(n lg n) time, wouldn't that give me a different answer? Commented Oct 17, 2023 at 1:39
• Sorting the unsorted section would be $O(f(n)lg f(n))$ that is $O(lg n lg lg n)$. After merging, everything is sorted.
– holf
Commented Oct 17, 2023 at 1:51
• The running time of sorting the $O(\log n)$ unsorted elements using any comparison-based operation will not affect the total running time of merging the originaly sorted and the newly sorted elements. Commented Oct 17, 2023 at 1:54
• @Derek, “Do you know mergesort” doesn’t tell you to use mergesort, it tells you to look at the mergesort algorithm and see what part of it solves your problem in O(n). Commented Oct 18, 2023 at 12:35

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)$$.

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.