Chapter 1
Getting Things in Order with Mergesort

One of the most fundamental concepts central to understanding data structures and algorithms is understanding time complexity. A Common-Sense Guide to Data Structures and Algorithms in Python, Volume 1 discussed this at great length, placing heavy emphasis on the use of Big O notation as a tool for articulating the speed of algorithms. Volume 2 takes things to the next level and adds more nuance to the conversation of time complexity. You’ll learn that while counting an algorithm’s steps and Big O serve as an important model for measuring time complexity, that’s not the full story. This is because there are additional factors that can affect an algorithm’s “true” speed. In this chapter, we’ll take a look at one of those factors.

We’ll also contrast two of the most famous “fast” sorting algorithms—Quicksort and Mergesort—and use the contrast to tease out the limits of the Big O model. Quicksort was covered in Volume 1, Chapter 13, and Mergesort is the main focus of this chapter. We’ll look at basic array merges and then discover how they form the backbone of Mergesort. From there, we’ll have an important conversation about algorithmic trade-offs. Finally, you’ll discover how the counting-steps model is not the end-all of determining an algorithm’s true speed.

Ready? Let’s dive in.