Select using median of medians

gistfile1.txt

def select(ls,i):
	'''select the ith order stat of the list ls'''

	subs = [sorted(ls[i:i+5]) for i in xrange(0,len(ls),5)] #partition in n/5 groups of length at most 5 each

	median_ls = [sub[len(sub)/2] for sub in subs]
	

	print "median",median_ls
	pivot = select(median_ls,len(median_ls)/2) #pivot is the median of medians
	
	#partition array around the pivot
	low = [j for j in ls if j <= pivot]
	high = [j for j in ls if j > pivot]
	
	
	k = len(low)
	if i < k:
		"recursive low"
		return	select(low,i)
	elif i > k:
		print "recursive high"
		return select(high,i-k-1)
	else:
		return pivot