84. Quick Sort

Given an array of n integers, sort it in ascending order using the quicksort algorithm (pick a pivot, partition the array around it, then recursively sort each side) and print the result.

Input: The first line contains an integer n. The second line contains n space-separated integers, the array to sort. Output: Print the sorted array in ascending order, space-separated, on one line.

1 <= n <= 10^5

Quicksort sorts IN PLACE (no second array needed, unlike merge sort) - this smaller memory footprint is a major reason it's often preferred in practice despite merge sort's more consistent worst-case guarantee.

Pick one person from a crowd as a reference point. Ask everyone shorter than them to stand on the left, everyone taller to stand on the right. Now repeat this same process separately within the left group and the right group, until every small group is naturally in order. Brute force: A simpler sort like selection sort or bubble sort repeatedly scans for the next smallest element or swaps adjacent out-of-order pairs, costing O(n²) comparisons in the worst case - correct, but slow for large arrays. Optimised: Quicksort's partitioning step does real, useful work in one pass (correctly placing the pivot AND roughly halving the remaining problem), and because it recurses on two SMALLER, independent sub-problems, the total work averages out to O(n log n) - the same 'divide and conquer' family as merge sort, just partitioning around a pivot instead of splitting exactly in half.

Repeatedly scan the unsorted portion of the array to find the minimum remaining element and swap it into the current front position, then move the boundary of the sorted portion forward by one. This is simple and always correct, but for every one of the n positions it performs a full linear scan of the remaining elements, giving quadratic time regardless of the input's initial order. Time: O(n^2) Space: O(1)

Recursively split the array in half until each piece has a single element, then merge sorted halves back together by repeatedly taking the smaller of the two fronts. This guarantees log n levels of splitting with a linear amount of merge work at each level regardless of how the input is arranged, which is a genuine algorithmic improvement over selection sort's quadratic worst case, at the cost of needing an auxiliary array to hold elements during merging. Time: O(n log n) Space: O(n)

Pick a pivot (chosen randomly, or via median-of-three, to avoid consistently bad choices), partition the array in place so elements smaller than the pivot end up to its left and larger ones to its right, then recursively sort each side. Because the partitioning is done in place rather than into a new merged array, quicksort needs only logarithmic auxiliary space for the recursion stack instead of merge sort's linear auxiliary array, and its typically excellent cache locality makes it faster in practice on average, which is why it's the standard choice here; randomizing the pivot keeps the expected time at n log n and makes an adversarial O(n^2) worst case extremely unlikely. Time: O(n log n) Space: O(log n)

1. Choose a pivot element from the array (commonly the last element). 2. Partition: rearrange the array so everything smaller than the pivot ends up to its left, everything larger ends up to its right, and the pivot lands in its final correct sorted position. 3. Recursively apply the exact same process to the left partition and the right partition independently. 4. Once every partition has shrunk down to a single element (or is empty), the whole array is sorted.

Time: On average, n times log n - genuinely fast in practice for typical inputs. In the worst case (a consistently unlucky pivot choice, like an already-sorted array with the last element always chosen as pivot), it degrades to n squared, which is why real implementations often pick a random or median-ish pivot to avoid this. Space: O(log n) on average, for the recursive call stack (no extra array is needed - partitioning happens in place); this can grow to O(n) in the worst-case unbalanced-partition scenario.

n = 1 (a single element, trivially sorted); an already-sorted or reverse-sorted array, a worst case for a naive pivot choice; n = 10^5 for performance; duplicate values, which aren't excluded by the constraints.

Be ready to explain WHY quicksort can degrade to O(n²) (a poor, consistently unbalanced pivot choice) and how real implementations mitigate it (randomized pivot selection, or median-of-three) - this distinguishes genuine understanding from memorized steps.