Sorting as a Key to Other Algorithms

As of this writing, the fastest sorting algorithms we know of have speeds of O(N log N). While Quicksort is one of the most popular among them, there are many others as well. Mergesort is another well-known O(N log N) sorting algorithm and will be covered in Volume 2 of this book.

The fact that the fastest sorting algorithms are O(N log N) is important, as this has implications for other algorithms as well. This is because there are algorithms that use sorting as a component of a larger process.

For example, if you’ll recall from Chapter 4, , we dealt with the problem of checking whether there are duplicate values within an array.

The first solution we looked at involved nested loops and had an efficiency of O(N²). While we found a solution that took O(N), I parenthetically hinted at a disadvantage with that approach having to do with extra memory consumption. (I’ll eventually discuss this at length in Chapter 19, .) So let’s assume that the O(N) approach is out. Are there any other ways we can improve upon the quadratic O(N²) solution? Hint: the solution has something to do with sorting!

We can build a beautiful algorithm if we presort the array.

Let’s say the original array was [5, 9, 3, 2, 4, 5, 6]. This array has two instances of 5, so we do have a case of duplicates.

Now, if we first sorted this array, it would become [2, 3, 4, 5, 5, 6, 9].

Next, we can use a single loop to iterate over each number. As we inspect each number, we’d check whether it’s identical to the next number. If it is, we’ve found a duplicate. If we get to the end of the loop without finding a duplicate, then we know that we have no duplicates.

The trick here is that by presorting the numbers, we end up bunching duplicate numbers together.

In our example, we’d start by looking at the first number, which is the 2. We’d check whether it’s identical to the next number. The next number is 3, so they’re not duplicates.

We’d then check the 3 against the following number, which happens to be a 4, allowing us to move on. We’d check the 4 against the 5, and we’d move on again.

At this point, we’d inspect the first 5 and check it against the following number, which is the second 5. Aha! We found a pair of duplicate numbers, and we can return true.

Here’s a Python implementation of this:

Now, this is an algorithm that used sorting as one of its components. What’s the Big O of this algorithm?

We start out by sorting the array. We can assume that Python’s sort() function uses something like Quicksort under the hood and has an efficiency of O(N log N). Next, we spend up to N steps iterating through the array. Our algorithm, then, takes (N log N) + N steps.

You learned that when we have multiple orders added together, Big O notation keeps only the highest order of N because the lower orders are trivial beside the higher orders. Here as well, N is trivial beside N log N, so we reduce the expression to O(N log N).

So, that’s it! We’ve used sorting to develop an algorithm that is O(N log N), which is a significant improvement over the original O(N²) algorithm.

Plenty of algorithms employ sorting as part of a larger process. We now know that any time we do so, we have an algorithm that is at least O(N log N). Of course, the algorithm may be slower than this if it has other things going on, but we know that O(N log N) will always be the baseline.