Head First Algorithms and Data Structures

Chapter 5. Sorting: Sorting Things Out

A Note for Early Release Readers

With Early Release ebooks, you get books in their earliest form—the author’s raw and unedited content as they write—so you can take advantage of these technologies long before the official release of these titles.

This will be the 5th chapter of the final book.

If you’d like to be actively involved in reviewing and commenting on this draft, please reach out to the editor at [e-mail].

If you’ve got a sorted list, you’ve got a data structure that makes lookups fast and lets binary search work in O(log n) time. That’s pretty powerful; but, to get 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 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 we’ve treated our arrays as already sorted when we used tricks like binary search, but arrays don’t sort themselves, so someone has to do the work of sorting. How do we do that?

We’ll begin by sorting in ...