Randomized Quick Sort in python

	from random import randint
	def inPlaceQuickSort(A,start,end):
	if start<end:
	pivot=randint(start,end)
	temp=A[end]
	A[end]=A[pivot]
	A[pivot]=temp
	p=inPlacePartition(A,start,end)
	inPlaceQuickSort(A,start,p-1)
	inPlaceQuickSort(A,p+1,end)
	def inPlacePartition(A,start,end):
	pivot=randint(start,end)
	temp=A[end]
	A[end]=A[pivot]
	A[pivot]=temp
	newPivotIndex=start-1
	for index in xrange(start,end):
	if A[index]<A[end]:#check if current val is less than pivot value
	newPivotIndex=newPivotIndex+1
	temp=A[newPivotIndex]
	A[newPivotIndex]=A[index]
	A[index]=temp
	temp=A[newPivotIndex+1]
	A[newPivotIndex+1]=A[end]
	A[end]=temp
	return newPivotIndex+1
	X=[4,5,7,4,3,6,0,4,22,45,82]
	inPlaceQuickSort(X,0,len(X)-1)
	#X=[0, 3, 4, 4, 4, 5, 6, 7, 22, 45, 82]

view raw randomizedquicksort.py hosted with ❤ by GitHub

MergeSort in python

	def mergeSort(A):
	if len(A)>1:
	[x1,x2]=divide(A)
	#print x1,x2
	x1,leftInv=mergeSort(x1)
	x2,rightInv=mergeSort(x2)
	#print leftInv,rightInv
	merged,splitInv=merge(x1,x2)
	#print splitInv
	return merged,(leftInv+rightInv+splitInv)
	else:
	return A,0
	def divide(A):
	size=len(A)
	halfSize=size/2
	x1=[]
	x2=[]
	for index in xrange(0,halfSize):
	x1.append(A[index])
	for index in xrange(halfSize,size):
	x2.append(A[index])
	return [x1,x2]
	def merge(x1,x2):
	x=[]
	x1Index=0
	x2Index=0
	invCount=0
	size1=len(x1)
	size2=len(x2)
	while ( x1Index < size1 and x2Index < size2):
	if x1[x1Index]<=x2[x2Index]:
	x.append(x1[x1Index])
	x1Index=x1Index+1
	else:
	x.append(x2[x2Index])
	x2Index=x2Index+1
	invCount += (size1-x1Index)
	for i in range(x1Index,size1):
	x.append(x1[i])
	for i in range(x2Index,size2):
	x.append(x2[i])
	return x,invCount
	a=[6,5,4,3,2,1]
	print 'before sorting',a
	x=mergeSort(a)
	print 'after sorting',x

view raw mergesort.py hosted with ❤ by GitHub