quick_sort.py

def quick_sort(m, sort_by):
	def partition(m, lo, hi):
		p = m[hi]	# choose a pivot
		i = lo
		for j in range(lo, hi):
			if sort_by(m[j], p):
				m[i], m[j] = m[j], m[i]
				i += 1
		m[i], m[hi] = m[hi], m[i]
		return i

	def _quick_sort(m, lo, hi):
		if lo < hi:
			p = partition(m, lo, hi)
			_quick_sort(m, lo, p-1)
			_quick_sort(m, p+1, hi)

	m = list(m)	# deep copy
	_quick_sort(m, 0, len(m)-1)

	return m