# Quick Sort (122A)

The idea of quick sort is:

function QuickSort(A[1...n]):
	pivotValue = ChoosePivot()

	partitionLeft = from A select value where value < pivot value
	partitionMid = from A select value where value == pivot value
	partitionRight = from A select value where value > pivot value
	
	Recursively sort partitionLeft           // *Recursion Magic*
	Recursively sort partitionRight          // *Recursion Magic*

# Base Case

When A has 1 or 0 elements, we do nothing.

# Partition

partitionLeft = from A select value where value < pivot value

↑ This partitioning step is doing most of the work.

Unlike merge sort, after left & right partitions are sorted, the merging step is already done.

Similar to how we considered merge(), it’s easier to think about if we use extra space.

function Partition(A[1...n], pivotValue) -> (List, List):
	left = []
	right = []

	for i = 1 to n:
		if A[i]	< pivotValue:
			push A[i] into left
		else if A[i] == pivotValue: 
			if not first time seeing pivotValue:
				push A[i] into left
		else:
			push A[i] into right

	return left, right

(Change < to other predicates depending on the sorting order)

This is also a linear scan, so the runtime is O(n).

# Choosing the Pivot

There are a lot of ways for choosing pivots:

Always pick first
Always pick last
Choose randomly
Somehow pick out the true median of A (important for quick select)

Source

# Pseudocode

function QuickSort(A[1...n]) -> Array:
	if n > 1: 
		pivot_value = ChoosePivot()
		left, right = Partition(A[1...n], pivot_value)
		return flatten([QuickSort(left), [pivot_value], QuickSort(right)])
	else:
		return A

function Partition(A[1...n], pivot_value) -> pair of Arrays:
	left = []
	right = []

	for i = 1 to n:
		if A[i]	< pivot_value:
			push A[i] into left
		else if A[i] == pivot: 
			if not first time seeing pivot:
				push A[i] into left
		else:
			push A[i] into right

	return left, right

function ChoosePivot() -> int:
	// depends on implementation, assume this is O(1)
	return pivot

# Python

Github