07aSorting
Database Management
13 May 2026
Sorting is ubiquitous in computers
- Knuth (1998) is completely devoted to sorting and searching
- These tasks are everywhere in computers
- If you want to search a list, the way is a linear search, examining each item in turn, one at a time
- That’s painfully slow, especially if the item is near the end of the list
- It might be better to sort the items so we can look through them faster
Aside: binary search
- How can we search faster than linear search?
- Go at once to the middle of a sorted list (assuming we know how many items there are in the list)
- Check to see which half of the list contains the item
- Divide that half of the list in half and check again
- For a thousand items, it takes ten or fewer steps
- For a million items, it takes twenty or fewer steps
Sorting states
- To use binary search, we first need to sort the list
- How we will sort depends on the current state of the list
- Four common states are: random, few unique, reversed, almost sorted
- We can often make a good guess about the state of a particular column
- Then we can apply a sorting algorithm to the list
Sorting algorithms
- There are many sorting algorithms, none of which is best for all states
- We’ll look at nine algorithms, including
- quicksort (the most commonly used)
- insertion sort
- heap sort
- merge sort
- bubble sort (generally the worst but often taught because it’s easy to describe)
- and more
Visualizing the algorithms
Now watch the following video comparing nine sorting algorithms (it has no ads!).
Observations
- You should be convinced that no sorting algorithm dominates the others in all four displayed states
- It should be obvious that you would never use bubble sort (but students sometimes do because it’s the easiest to program)
- For very long lists, you probably don’t want to move items around because of space constraints
- In google interviews they like to ask you to sort a billion integers and the correct answer is first to find out if the integers will fit into memory, second, if they do, find out if they fit into a specific range or if they are all distinct, and, if they don’t fit, use an external sort. If they do fit, possibly a radix sort is best but always ask as many qualifying questions as you are allowed
Next up
You will learn why a database user cares about searching and sorting and selecting algorithms, which you rarely need to do by hand
But, if you have to sort a list of items prior to putting them into SQLite, usually using the Unix sort command (available on all platforms) is an adequate answer
END
References
Knuth, Donald E. 1998. The Art of Computer Programming, Volume 3: (2nd Ed.) Sorting and Searching. Addison Wesley Longman Publishing Co., Inc.
Colophon
This slideshow was produced using quarto
Fonts are Roboto, Roboto Light, and Victor Mono Nerd Font
