Source code online books for professionals by professionals

Listing 6-4.  Quicksort
def quicksort(seq):
    if len(seq) <= 1: return seq                # Base case
    lo, pi, hi = partition(seq)                 # pi is in its place
    return quicksort(lo) + [pi] + quicksort(hi) # Sort lo and hi separately
 
As you can see, the algorithm is simple, as long as you have partition in place. (Exercises 6-11 and 6-12 ask 
you to rewrite quicksort and partition to yield an in-place sorting algorithm.) First, it splits the sequence into those 
we know must be to the left of pi and those that must be to the right. These two halves are then sorted recursively 
(correct by inductive assumption). Concatenating the halves, with the pivot in the middle, is guaranteed to result in a 
sorted sequence. Because we’re not guaranteed that partition will balance the recursion properly, we know only that 
quicksort is loglinear in the average case—in the worst case it’s quadratic.
6
Quicksort is an example of a divide-and-conquer algorithm that does its main work before the recursive calls, 
in dividing its data (using partition). The combination part is trivial. We can do it the other way around, though: 
trivially split our data down the middle, guaranteeing a balanced recursion (and a nice worst-case running time), and 
then make an effort at combining, or merging the results. This is exactly what merge sort does. Just like our skyline 
algorithm from the beginning of this chapter goes from inserting a single building to merging two skylines, merge sort 
goes from inserting a single element in a sorted sequence (insertion sort) to merging two sorted sequences.
You’ve already seen the code for merge sort in Chapter 3 (Listing 3-2), but I’ll repeat it here, with some comments 
(Listing 6-5).
Listing 6-5.  Merge Sort
def mergesort(seq):
    mid = len(seq)//2                           # Midpoint for division
    lft, rgt = seq[:mid], seq[mid:]
    if len(lft) > 1: lft = mergesort(lft)       # Sort by halves
    if len(rgt) > 1: rgt = mergesort(rgt)
    res = []
6
In theory, we could use the guaranteed linear version of select to find the median and use that as a pivot. That’s not something 
likely to happen in practice, though.

---

Chapter 6 
■
 DiviDe, Combine, anD Conquer
126
    while lft and rgt:                          # Neither half is empty
        if lft[-1] >=rgt[-1]:                   # lft has greatest last value
            res.append(lft.pop())               # Append it
        else:                                   # rgt has greatest last value
            res.append(rgt.pop())               # Append it
    res.reverse()                               # Result is backward
    return (lft or rgt) + res                   # Also add the remainder
 
Understanding how this works should be a bit easier now than it was in Chapter 3. Note the merging part has 
been written to show what’s going on here. If you were to actually use merge sort (or a similar algorithm) in Python, 
you would probably use heapq.merge to do the merging.