#!/usr/bin/python

def quick_sort(list_, stable=False):
	if stable:
		stable_quick_sort(list_)
	else:
		unstable_quick_sort(list_)

def stable_quick_sort(list_):
	length = `len'(list_)
	# decorate, sort, undecorate - to make it stable
	decorated = []
	for index, value in enumerate(list_):
		decorated.append((value, index))
	del list_[:]
	quick_sort_c(decorated, 0, length - 1)
	for value, index in decorated:
		list_.append(value)

def unstable_quick_sort(list_):
	length = `len'(list_)
	quick_sort_c(list_, 0, length - 1)

ifdef(m4pyx,c)def insertion_sort(list_, ifdef(m4pyx,int )left, ifdef(m4pyx,int) right):
	ifdef(m4pyx,cdef int i)
	ifdef(m4pyx,cdef int j)
	for i in xrange(left+1, right+1):
		j = i
		temp = list_[j]
		while j > 0 and list_[j-1] > temp:
			list_[j] = list_[j-1]
			j -= 1
		list_[j] = temp

ifdef(m4pyx,c)def is_inorder(list_, ifdef(m4pyx,int) left, ifdef(m4pyx,int) right):
	ifdef(m4pyx,cdef int index)
	for index in xrange(left, right - 1):
		if list_[index] > list_[index+1]:
			return False
	return True

ifdef(m4pyx,c)def is_reverseorder(list_, ifdef(m4pyx,int) left, ifdef(m4pyx,int) right):
	ifdef(m4pyx,cdef int index)
	for index in xrange(left, right - 1):
		if list_[index] < list_[index+1]:
			return False
	return True

ifdef(m4pyx,c)def reverse_order(list_, ifdef(m4pyx,int) left, ifdef(m4pyx,int) right):
	ifdef(m4pyx,cdef int width)
	ifdef(m4pyx,cdef int index)
	width = right - left + 1
	for index in xrange(width / 2):
		left_index = left + index
		right_index = right - index
		list_[left_index], list_[right_index] = list_[right_index], list_[left_index]

ifdef(m4pyx,c)def quick_sort_c(list_, ifdef(m4pyx,int) left, ifdef(m4pyx,int) right):
	# How many values?
	ifdef(m4pyx,cdef int num_values)
	ifdef(m4pyx,cdef int pivot_index)
	ifdef(m4pyx,cdef int store_index)
	num_values = right - left + 1
	# 31 is arbitrary and is perhaps something to tune
	if num_values < 31:
		insertion_sort(list_, left, right)
	else:
		if right > left:
			sample_values = []
			quarter = num_values / 4
			for index in [ left, left + quarter, left + num_values / 2, left + quarter * 3, right ]:
				sample_values.append((list_[index], index))
			length_of_sample_values_m1 = `len'(sample_values) - 1
			if is_inorder(sample_values, 0, length_of_sample_values_m1):
				if is_inorder(list_, left, right):
					return
			elif is_reverseorder(sample_values, 0, length_of_sample_values_m1):
				if is_reverseorder(list_, left, right):
					reverse_order(list_, left, right)
					return
			insertion_sort(sample_values, 0, 4)
			pivot_index = sample_values[2][1]
			# the number of ways we split this is arbitrary and perhaps something to tune.  It's traditional to split in half, but is that best?
			store_index = partition(list_, left, right, pivot_index)
			quick_sort_c(list_, left, store_index - 1)
			quick_sort_c(list_, store_index + 1, right)

ifdef(mypyx,c)def partition(list_, ifdef(m4pyx,int) left, ifdef(m4pyx,int) right, ifdef(m4pyx,int) pivot_index):
	ifdef(m4pyx,cdef int store_index)
	ifdef(m4pyx,cdef int i)
	pivot_value = list_[pivot_index]
	# Move pivot to end
	list_[pivot_index], list_[right] = list_[right], list_[pivot_index]
	store_index = left
	# left <= i < right  
	for i in xrange(left, right):
		if list_[i] <= pivot_value:
			list_[i], list_[store_index] = list_[store_index], list_[i]
			store_index += 1
	# Move pivot to its final place
	list_[store_index], list_[right] = list_[right], list_[store_index]
	return store_index