Understanding Quicksort

Quicksort is an efficient, comparison-based sorting algorithm. It follows the divide-and-conquer paradigm.

How it Works:

1. Pick a Pivot: Choose an element from the array as the pivot. Common strategies include picking the first, last, median, or a random element.
2. Partitioning: Rearrange the array so that all elements smaller than the pivot come before it, and all elements greater than the pivot come after it. After partitioning, the pivot is in its final sorted position.
3. Recursion: Recursively apply the above steps to the sub-array of elements with smaller values and separately to the sub-array of elements with greater values.

Complexity:

• Best Case: O(n log n) - Occurs when the pivot element always divides the array into two roughly equal halves.
• Average Case: O(n log n)
• Worst Case: O(n²) - Occurs when the pivot element is consistently the smallest or largest element (e.g., in an already sorted array if the first/last element is chosen as pivot).
• Space Complexity: O(log n) average (due to recursion stack), O(n) worst case.