Source code online books for professionals by professionals

Randomized select. Finds the median, or, in general, the kth order statistic (the kth smallest element). Works sort of 
like “half a quicksort.” It chooses a pivot element at random (or arbitrarily) and partitions the other elements to the left 
(smaller elements) or right (greater elements) of the pivot. The search then continues in the right portion, more or less 
like binary search. Perfect bisection is not guaranteed, but the expected running time is still linear. (See Listing 6-3.)
Select. The rather unrealistic, but guaranteed linear, sibling of randomized select. It works as follows: Divide the 
sequence into groups of five. Find the median in each using insertion sort. Find the median of these medians 
recursively, using select. Use this median of medians as a pivot and partition the elements. Now run select on the 
proper half. In other words, it’s similar to randomized select—the difference is that it can guarantee that a certain 
percentage will end up on either side of the pivot, avoiding the totally unbalanced case. Not really an algorithm you’re 
likely to use in practice, but it’s important to know about. (See Chapter 6.)
Selection sort. A simple sorting algorithm with quadratic running time. Very similar to insertion sort, but instead of 
repeatedly inserting the next element into the sorted section, you repeatedly find (that is, select) the largest element in 
the unsorted region (and swap it with the last unsorted element). (See Listing 4-4.)
Timsort. A super-duper in-place sorting algorithm based on mergesort. Without any explicit conditions for handling 
special cases, it is able to take into account partially sorted sequences, including segments that are sorted in reverse, 
and can therefore sort many real-world sequences faster than what would seem possible. The implementation in 
list.sort and sorted is also really fast, so if you need to sort something, that’s what you should use. (See the “Black 
Box” sidebar on timsort in Chapter 6.)