Quicksort is divide and conquer sorting algorithm.

A quick sort first selects a value, which is called the pivot value.

The role of the pivot value is to assist with splitting the list.

The actual position where the pivot value belongs in the final sorted list, commonly called the split point, will be used to divide the list for subsequent calls to the quick sort.

Expected Running time:O(nlogn)

Worstcase :O(n^2)

Advantages:

1.Good Cache Performance

2.Good Parallel Performance

Quick sort has two phase:

def partition(myList, start, end):

pivot = myList[start]

left = start+1

right = end

done = False

while not done:

while left <= right and myList[left] <= pivot:

left = left + 1

while myList[right] >= pivot and right >=left:

right = right -1

if right < left:

done= True

else:

# swap places

temp=myList[left]

myList[left]=myList[right]

myList[right]=temp

# swap start with myList[right]

temp=myList[start]

myList[start]=myList[right]

myList[right]=temp

return right

def quicksort(myList, start, end):

if start < end:

# partition the list

pivot = partition(myList, start, end)

# sort both halves

quicksort(myList, start, pivot-1)

quicksort(myList, pivot+1, end)

return myList

**Working:**A quick sort first selects a value, which is called the pivot value.

The role of the pivot value is to assist with splitting the list.

The actual position where the pivot value belongs in the final sorted list, commonly called the split point, will be used to divide the list for subsequent calls to the quick sort.

Expected Running time:O(nlogn)

Worstcase :O(n^2)

Advantages:

1.Good Cache Performance

2.Good Parallel Performance

Quick sort has two phase:

**1.Partition Phase**def partition(myList, start, end):

pivot = myList[start]

left = start+1

right = end

done = False

while not done:

while left <= right and myList[left] <= pivot:

left = left + 1

while myList[right] >= pivot and right >=left:

right = right -1

if right < left:

done= True

else:

# swap places

temp=myList[left]

myList[left]=myList[right]

myList[right]=temp

# swap start with myList[right]

temp=myList[start]

myList[start]=myList[right]

myList[right]=temp

return right

**2.Sort Phase**def quicksort(myList, start, end):

if start < end:

# partition the list

pivot = partition(myList, start, end)

# sort both halves

quicksort(myList, start, pivot-1)

quicksort(myList, pivot+1, end)

return myList