Tip 70 Sort Big in Place

Pythonic Programming — by Dmitry Zinoviev (82 / 116)

👈 Checkpoint, It Saves Time | TOC | Delete Your Garbage 👉

★★2.7, 3.4+ Sorting and searching are arguably the two most frequent and important operations in modern computing. They are so frequent that the second most valuable tech company globally, Alphabet (also known as Google), made its fortune on sorting and searching. They are so important that Python has two functions for sorting lists: list.sort and sorted. What is the difference?

First, sorted sorts any iterable but list.sort sorts only lists. Given Python’s obsession with lists, this does not seem to be a problem.

Second, sorted creates a sorted copy of the original iterable. When it returns, you get two iterables: the original and the sorted. That is both a curse and a blessing. It is a curse because you need twice as much memory — not a big deal from a small list but a significant issue for a large dataset. When you have a list of one billion items, you may wonder if you want to copy it. As a form of compensation, you can still access the list items in the original order.

list.sort sorts the list in place. It shuffles the list items around without making a copy. If you could load the list into memory, you can surely afford to sort it. However, list.sort ruins the original order. Interestingly, the two sorting tools have approximately the same performance.