For a long time, quicksort was seen as the best way to implement a general sorting algorithm. Quicksort works as follows:

• It first selects one number from the list, which is called the “pivot”.
• It then moves all items bigger than the pivot to the back of the list, and all items smaller than the pivot to the front. This is called the “partition operation”, and leads to the pivot being in its final place.
• Then the quicksort procedure is recursively repeated for the partitions. The recursion ends when a partition is of size 1 or less.

Note that the choice of pivot is important for the efficiency of the algorithm. A common choice is to simply take the last element of the list, but depending on the data, a different choice might be apt.

The following is a very efficient in-place implementation of quicksort.

# This function creates two partitions around the pivot.
# The partitions are created in a sublist of tlist, namely between index lo and hi.
# Pivot is selected as the last item.
# The function then makes sure that all elements higher than pivot are at the end.
# Finally, it puts pivot between the two partitions, and returns the position of pivot.
def partition( tlist, lo, hi ):
    pivot = tlist[hi]
    i = lo - 1    
    for j in range( lo, hi ):
        if tlist[j] < pivot:
            i += 1
            tlist[i], tlist[j] = tlist[j], tlist[i]
    if tlist[hi] < tlist[i+1]:
        tlist[i+1], tlist[hi] = tlist[hi], tlist[i+1]
    return i+1

# This recursive function applies quicksort to tlist, between index lo and index hi.
def qs( tlist, lo, hi ):
    if lo < hi:
        p = partition( tlist, lo, hi )
        qs( tlist, lo, p-1 )
        qs( tlist, p+1, hi )

def quicksort( tlist ):
    qs( tlist, 0, len( tlist )-1 )
        
numlist = [8, 3, 5, 11, 5, 33, 2, 2, 0, 9, 12, 26, 1, 9, 18]
quicksort( numlist )
print( numlist )

Quicksort is O(n*log(n)), i.e., the same as merge sort. However, it tends to be two to three times faster than merge sort. Moreover, as the algorithm above shows, it can be easily implemented as an in-place procedure.

A disadvantage of quicksort is that it is “unstable”. This means that if two elements of the list are considered of equal value, then after sorting they might have switched places. This does not matter for lists of numbers, of course, but if you want to sort, for instance, a deck of cards according to card value, and the 5 of Clubs is earlier in the deck than the 5 of Diamonds, then you might want to keep them in that order. With quicksort, it is no saying what their final order will be.

Naturally, quicksort also shares merge sort’s disadvantages that come with it being recursive. However, the in-place implementation at least is very light on memory and stack usage.