Quick Sort

def quick_sort(a, lo=0, hi=None):
    if hi is None:
        hi = len(a) - 1
    if lo < hi:
        pivot, i = a[hi], lo
        for j in range(lo, hi):
            if a[j] < pivot:
                a[i], a[j] = a[j], a[i]
                i += 1
        a[i], a[hi] = a[hi], a[i]
        quick_sort(a, lo, i - 1)
        quick_sort(a, i + 1, hi)

Average $O(n \log n)$, sorts in place and is very fast in practice. A bad pivot (e.g. already-sorted data with the last element as pivot) gives $O(n^2)$; random or median-of-three pivots avoid this.