Quick Sort (OCR A-Level Computer Science): Flashcards

Divide-and-conquer

Comparison-based sorting

Splits array: smaller left, larger right

Minimal additional memory required

$O(n \log n)$

$O(n^2)$

Pivot divides array poorly

Choose a pivot

Partition array around pivot

Recursively apply to sub-arrays

First, last, or middle element

Random pivot or median-of-three