Quick Sort

overview

Remember these Terms

• Pivot: the chosen value used to split the array.
• Partition: rearrange items so smaller left, larger right.
• Divide and Conquer: solve subarrays around the pivot recursively.
• Recursion: function calls itself on subproblems.
• Base Case: stop when subarray has zero or one element.
• In-place: sorts using small extra array space.
• Time Complexity: average O(n log n), worst O(n^2).
• Stability: not stable; equal items may change order.
• Pivot Selection: choose first, last, middle, or random element.
• Partition Scheme: Lomuto and Hoare are common ways to partition.