Head First Algorithms and Data Structures

Chapter 5. Sorting: Sorting Things Out

If you have a sorted list, you have a data structure that makes lookups fast and lets binary search work in O(log n) time. That’s pretty powerful, but to use that power you need a sorted list. After all, we can’t always assume we have one. In this chapter you’ll learn how to bubble, merge, and pivot your way into some sorted data structures. We’ll also get acquainted with a new O(n log n) time complexity and a sorting speed limit. We’ll finish it all up with Timsort, an interesting hybrid sorting algorithm many languages use as their default sort algorithm. Let’s get sorting!

How to sort an array

So far, when we used tricks like binary search, we’ve treated our arrays as already sorted. But arrays don’t sort themselves, so someone has to do the work of sorting. How do we do that?

We’ll begin with a simple sort: we’ll traverse the array left to right, always looking at two neighbors. If the two are in the wrong order (that is, they aren’t sorted), we swap them. Then we slide to the next two items and repeat. After one full pass, we’ll see the largest item has drifted to the far right. We do another pass and the next-largest drifts right. We keep going until a pass makes no swaps; that’s our “done” signal. Let’s walk through an example ...