Why Not Sort Only When We Search?

Keeping the array sorted at all times is what makes SortedArray’s add expensive. We could leave the array unsorted, keep the $O(1)$ adds, and sort the array only when we actually need to search it.

Now that we have the notion of Big-Oh, we can analyze that idea. Let’s say we have an array of $n$ elements. We want to search it once. The plan is to sort it first and then binary search it. What is the Big-Oh of that plan?

The selection sort we analyzed earlier is $O(n^2)$. There are faster sorting algorithms that run in $O(n\log n)$ time, and we will study them later in the course. Let’s use the faster figure, $O(n\log n)$, so the idea gets the lowest sorting cost available. Even then, sorting an array costs more than a single linear scan of it, which is $O(n)$.

Sorting the array for a single search is worse than not sorting at all. So when is sort-on-demand worth it? Only if we sort once and then search many times, with no changes to the array in between. Then the $O(n\log n)$ is paid once and shared across all those searches, and each search after the first is only $O(\log n)$. This is the same trade-off SortedArray makes. The only difference is when the sorting cost is paid. A SortedArray pays it a little at a time, $O(n)$ on every add. Sort-on-demand keeps adds at $O(1)$ and pays $O(n\log n)$ all at once, the next time someone searches after a change.

Which of those is better depends on the workload again. This time what matters is whether the adds and the searches are interleaved or come in bursts. If the data arrives in bulk and is then searched many times, sort once after it is loaded and you pay $O(n\log n)$ once. If adds and searches alternate, sort-on-demand is the worse choice, because every search that follows an add has to sort the whole array again. In that case keeping the array sorted on every add is better.