ts-ds / quickSort

Function: quickSort()

function quickSort<T>(array, compareFn?): void;

Defined in: sort/quick/quick.ts:31

Sorts an array in place using quick sort.

Divide and conquer: picks a pivot, partitions the range so that elements before the pivot are not greater and elements after it are not less, then sorts both parts recursively.

Details that make it reliable, as described by Hoare and Sedgewick:

• Hoare partitioning — two indexes move towards each other and swap elements that are on the wrong side. Both scans stop on elements equal to the pivot, so arrays with many duplicates are split evenly.
• Median-of-three pivot — the median of the first, middle and last element. Sorted and reversed arrays, the classic worst case for the "first/last element" pivot, become the best case.
• Recursion into the smaller part only, the larger part is handled by the loop — the call stack depth is at most O(log n) for any input.

The worst case O(n²) is still possible on specially crafted input. CLRS avoids it with high probability by choosing the pivot at random.

Time: best	Time: average	Time: worst	Memory	Stable	In place
O(n log n)	O(n log n)	O(n²)	O(log n)	no	yes

Type Parameters

Type Parameter	Description
T

Parameters

Parameter	Type	Default value	Description
array	T[]	undefined	Array to sort. It is modified.
compareFn?	CompareFn<T>	defaultCompare	Order of elements, ascending by default.

Returns

void

Nothing — array itself is sorted.