The Self-Taught Computer Scientist

4Sorting Algorithms

I think the bubble sort would be the wrong way to go.

Barack Obama

As a computer scientist, in addition to searching for data, you will often have to sort data. Sorting data means arranging it in a meaningful way. For example, if you have a list of numbers, you could sort them from the smallest to the largest (ascending). Or, imagine you are building an app that keeps track of the books each user has read. In an app like this, you might want to allow the user to see their books sorted in different ways. For example, you could give them the option to see their books sorted from the shortest book to the longest, oldest to newest, or newest to oldest.

There are many different sorting algorithms to help you sort data, each with strengths and weaknesses. For example, some sort algorithms work best in specific situations, like if an iterable is nearly sorted. In this chapter, you will learn about bubble sort, insertion sort, and merge sort. Other popular sorts include quicksort, shell sort, and heap sort. There are many sorting algorithms you will have to use in only rare circumstances, so after teaching you a few sorts, I spend the remainder of the chapter showing you how to use Python's built-in functions to sort data, something you will often use in real-world programming.

When you are building your programs in the real world, you should almost always use your programming language's built-in sorting function. You should not implement the classic sorting algorithms ...