cheatsheet-sorting.py
```
# The Sound of Sorting Algorithms in Python's Taste #

# 1
def bubble_sort(seq):
""" worst(n^2), best(n), avg(n^2)
stable: yes
"""
for passnum in range(len(seq) - 1, 0, -1):
for i in range(passnum):
if seq[i] > seq[i + 1]:
seq[i], seq[i + 1] = seq[i + 1], seq[i]

# 2
def selection_sort(seq):
""" worst(n^2), best(n^2), avg(n^2)
stable: no
"""
for i in range(len(seq) - 1):
mini, miniat = seq[i], i
for j in range(i + 1, len(seq)):
if seq[j] < mini: mini, miniat = seq[j], j
seq[i], seq[miniat] = seq[miniat], seq[i]

# 3
def ins_sort(seq):
""" worst(n^2), best(n), avg(n^2)
stable: yes
"""
for i in range(1, len(seq)):
j = i
while j > 0 and seq[j - 1] > seq[j]:
seq[j - 1], seq[j] = seq[j], seq[j - 1]
j -= 1

# 4
def partition(seq):
pi, seq = seq[0], seq[1:]
lo = [x for x in seq if x <= pi]
hi = [x for x in seq if x > pi]
return lo, pi, hi

def quicksort(seq):
""" worst(n^2), best(n lgn), avg(n lgn)
stable: no
"""
if len(seq) <= 1: return seq
lo, pi, hi = partition(seq)
return quicksort(lo) + [pi] + quicksort(hi)

# 5
def mergesort(seq):
""" worst(n lgn), best(n lgn), avg(n lgn)
stable: yes
"""
mid = len(seq) // 2
lft, rgt = seq[:mid], seq[mid:]
if len(lft) > 1: lft = mergesort(lft)
if len(rgt) > 1: rgt = mergesort(rgt)
res = []
while lft and rgt:
if lft[-1] >= rgt[-1]:
res.append(lft.pop())
else:
res.append(rgt.pop())
res.reverse()
return (lft or rgt) + res

# 6
def heapify(seq, i, n):
l, r = 2 * i + 1, 2 * (i + 1)
maxat = i
if l <= n and seq[l] > seq[i]:
maxat = l
if r <= n and seq[r] > seq[maxat]:
maxat = r
if maxat != i:
seq[i], seq[maxat] = seq[maxat], seq[i]
heapify(seq, maxat, n)

def buildheap(seq, s, n):
for i in range(s, -1, -1):
heapify(seq, i, n)

def heapsort(seq):
""" worst(n lgn), best(n lgn), avg(n lgn)
stable: no
"""
end = len(seq) - 1
start = end / 2
buildheap(seq, start, end)

for i in range(end, 0, -1):
seq[0], seq[i] = seq[i], seq[0]
end -= 1
heapify(seq, 0, end)

# Last updated: Thu May  8 00:53:29 EDT 2014, by: Aziz Altowayan, thnx: Python Algorithms (Hetland) and Wikipedia.
```