Python Cookbook

Chapter 2. Searching and Sorting

Introduction

Credit: Tim Peters, PythonLabs

Computer manufacturers of the 1960s estimated that more than 25 percent of the running time on their computers was spent on sorting, when all their customers were taken into account. In fact, there were many installations in which the task of sorting was responsible for more than half of the computing time. From these statistics we may conclude that either (i) there are many important applications of sorting, or (ii) many people sort when they shouldn’t, or (iii) inefficient sorting algorithms have been in common use.

—Donald Knuth, “The Art of Computer Programming”, Volume 3, Sorting and Searching, page 3

Professor Knuth’s masterful work on the topics of sorting and searching spans nearly 800 pages of sophisticated technical text. In Python practice, we reduce it to two imperatives (we read Knuth so you don’t have to):

• When you need to sort, find a way to use the built-in sort method of Python lists.

• When you need to search, find a way to use built-in dictionaries.

Many recipes in this chapter illustrate these principles. The most common theme is using the decorate-sort-undecorate (DSU) pattern, a general approach to transforming a sorting problem by creating an auxiliary that we can then sort with the default, speedy sort method. This is the single most useful technique to take from this chapter. It relies on an unusual feature of Python’s built-in comparisons: sequences are compared lexicographically.