def _partition(comparables, lo, hi):
	"""Return index upon partitioning the array pivoting on the first element

	Arguments:
	comparables -- an array of which the elements can be compared
	lo          -- lower bound of indices
	hi          -- higher bound of indices

	After partition, 
	elements to the left of pivot are no larger than the pivot;
	elements to the right of pivot are no smaller than the pivot.

	comparables[lo:j] <= pivot
	comparables[j+1:hi] >= pivot

	This design choice is essential for Nlog(N) performance for 
	duplicate keys. 
	"""
	i = lo + 1
	j = hi - 1
	while i < j:
		while i < hi and comparables[i] < comparables[lo]: i += 1
		while j > lo and comparables[j] > comparables[lo]: j -= 1
		if i < j:
			comparables[i], comparables[j] = comparables[j], comparables[i]
			i += 1 # essential for duplicate keys
			j -= 1 # essential for duplicate keys

	comparables[lo], comparables[j] = comparables[j], comparables[lo]
	return j