gen-briefly-explain-quicksort-and-its-pivot-and-one-common-misco-f664

Briefly explain quicksort and its pivot and one common misconception about it.

# Quicksort Brief Overview **How it works:** Quicksort is a divide-and-conquer sorting algorithm that: 1. Selects a **pivot** element from the array 2. Partitions the array so all elements smaller than the pivot go to its left, and larger elements go to its right 3. Recursively applies the same process to the left and right subarrays **The Pivot:** The pivot is a chosen element used as a reference point for partitioning. Common strategies include: - First or last element - Middle element - Random element - Median-of-three (best for avoiding worst cases) **Common Misconception:** Many people believe quicksort is *always* O(n log n), but it actually has a **worst-case time complexity of O(n²)**. This occurs when the pivot consistently produces highly unbalanced partitions (e.g., when the array is already sorted and you always pick the first element as pivot). The O(n log n) complexity is the *average* case, which is why quicksort is still highly valued in practice—especially with good pivot selection strategies.