Quick Sort: Performance King

Quick Sort is an in-place, divide-and-conquer algorithm. On average, it is the fastest sorting algorithm in the world. It works by selecting a 'Pivot' and partitioning the array so that everything smaller than the pivot is on the left.

1. O(N Log N) Average, O(N^2) Worst Case

If you pick a bad pivot (like the first element of a sorted array), Quick Sort crashes to O(N^2) speed. However, with a Random Pivot or a Median-of-Three pivot, the probability of hitting the worst-case is practically zero.

2. In-Place (Memory Efficient)

Unlike Merge Sort, Quick Sort uses only O(Log N) space (for the recursion stack). It sorts the array by physically swapping elements in the original memory block. This makes it cache-friendly and extremely fast for array-based data.

4. Interview Mastery

Q: "Is Quick Sort Stable? Why does it matter?"

Architect Answer: "No, Quick Sort is **Unstable**. The partitioning process involves 'long distance' swaps that can jump over equal elements, ruining their relative order. If you need a stable result, you must either use Merge Sort or modify Quick Sort to store the original index of every item, which increases memory usage. Most modern languages (like Java/C#) use a hybrid: **Dual-Pivot QuickSort** for primitive arrays and **Timsort (Merge-based)** for objects to preserve stability."