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 lo g n)$ time, and we will study them later in the course. Let’s use the faster figure, $O (n lo g 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 lo g n)$ is paid once and shared across all those searches, and each search after the first is only $O (lo g n)$ .

Compared with keeping a SortedArray, batching the adds can also reduce the total work. Suppose we start empty and add $n$ elements. In the worst case, each new element belongs at the front of a SortedArray, so the adds shift $0 + 1 + 2 + \dots + (n - 1)$ elements in total. That is the triangular sum we saw earlier: building the sorted array this way costs $O (n^{2})$ . Appending all $n$ elements to a DynamicArray costs $O (n)$ in total, including growth, and sorting once afterward costs $O (n lo g n)$ with the faster sorting algorithm assumed here. The total is $O (n lo g n)$ . Both approaches then support $O (lo g n)$ searches. Batching changes how much work we do, as well as when we do it.

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 lo g 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.