Source code online books for professionals by professionals

Sorting and element uniqueness. Sorting is an important operation and an essential subroutine for several other 
algorithms. In Python, you would normally sort by using the list.sort method or the sorted function, both of which 
use a highly efficient implementation of the timsort algorithm. Other algorithms include insertion sort, selection sort, 
and gnome sort (all of which have a quadratic running time), as well as heapsort, mergesort, and quicksort (which 
are loglinear, although this holds only in the average case for quicksort). For information on the quadratic sorting 
algorithms, see Chapter 5; for the loglinear (divide-and-conquer) algorithms, see Chapter 6. Deciding whether a set  
of real numbers contains duplicates cannot (in the worst case) be solved with a running time better than loglinear.  
By reduction, neither can sorting.

---

Appendix B 
■
 List of proBLems And ALgorithms
262