Quick Sort

Concept

Quick Sort is the most famous algorithm in computer science. Like Merge Sort, it uses the Divide and Conquer paradigm, achieving $O(N \log N)$ time.
Unlike Merge Sort, Quick Sort sorts everything In-Place (it swaps elements within the original array), completely avoiding the massive $O(N)$ memory overhead.

The magic of Quick Sort relies on a single concept: The Pivot.

The Mechanism

1. Pick a Pivot: Pick a random number from the array (usually the very last number) and declare it the “Pivot”.
2. Partitioning: Rearrange the entire array using two pointers so that:
   • Everything SMALLER than the Pivot is physically thrown to the Left side of the array.
   • Everything LARGER than the Pivot is thrown to the Right side of the array.
   • The Pivot is placed precisely in the middle.
3. The Guarantee: After one pass, the array is not sorted. BUT, the Pivot is now mathematically locked in its absolute, final, correct sorted position!
4. Recurse: The Pivot split the array into a Left chunk and a Right chunk. Recursively call Quick Sort on the Left chunk, and Quick Sort on the Right chunk.

Implementation

Quick Sort is notoriously difficult to code from memory in an interview because the Partitioning loop uses very specific pointer arithmetic.

// Time Complexity: O(N log N) Average, O(N^2) Absolute Worst Case
// Space Complexity: O(log N) Call Stack depth

function quickSort(nums: number[], left = 0, right = nums.length - 1): number[] {
    // Base Case: If the chunk is 1 element or less, it's perfectly sorted!
    if (left < right) {
        
        // Physically rearrange the array around a Pivot, and get the Pivot's locked index
        const pivotIndex = partition(nums, left, right);
        
        // Recurse on the Left Chunk (excluding the locked pivot)
        quickSort(nums, left, pivotIndex - 1);
        
        // Recurse on the Right Chunk (excluding the locked pivot)
        quickSort(nums, pivotIndex + 1, right);
    }
    
    return nums;
}

function partition(nums: number[], left: number, right: number): number {
    // Arbitrarily pick the extreme right element as our Pivot
    const pivotValue = nums[right];
    
    // i tracks the boundary of the "Smaller Than Pivot" zone
    let i = left;
    
    // Scan through the chunk
    for (let j = left; j < right; j++) {
        
        // If we find an element smaller than the Pivot...
        if (nums[j] < pivotValue) {
            // Throw it into the "Smaller" zone by swapping it with index i!
            [nums[i], nums[j]] = [nums[j], nums[i]];
            i++; // Expand the smaller zone
        }
    }
    
    // The loop finished. The "Smaller" zone boundary is at index i.
    // The Pivot is still sitting at the very end (right).
    // Swap the Pivot into index i, perfectly wedging it between the Small and Large halves!
    [nums[i], nums[right]] = [nums[right], nums[i]];
    
    // Return the mathematically locked position of the Pivot
    return i;
}

The $O(N^2)$ Worst-Case Disaster

Merge Sort is perfectly consistent: $O(N \log N)$ forever.
Quick Sort has a dark secret: Its theoretical worst-case time complexity is actually $O(N^2)$.

How?
Imagine the input array is already perfectly sorted: [1, 2, 3, 4, 5].

1. We pick the right-most element 5 as the Pivot.
2. We partition. Everything is smaller than 5, so the Left chunk is [1, 2, 3, 4]. The Right chunk is empty [].
3. Quick Sort recurses. It picks 4 as the pivot.
4. Left chunk is [1, 2, 3]. Right chunk is [].

Instead of cleanly splitting the array perfectly in half every time ($O(\log N)$ tree depth), it is just peeling off exactly one element per iteration! The recursion tree becomes a straight line of depth $N$, doing $N$ work at each level. $N \times N = O(N^2)$.

The Fix: Modern implementations never blindly pick the very last element. They use a “Median of Three” approach (looking at the first, middle, and last elements and picking the median as the pivot), or they pick a completely Math.random() pivot. This mathematically guarantees the array splits roughly in half, forcing the $O(N \log N)$ average case.

Interview Questions

Q: Is Quick Sort Stable?
A: No, Quick Sort is strictly Unstable. The act of violently swapping elements across the array during the Partition phase completely destroys the original relative order of identical elements.

Q: If Quick Sort’s worst case is $O(N^2)$, why is it the default algorithm in C++ (std::sort) and V8?
A: Cache Locality. Because Quick Sort swaps everything perfectly in-place within contiguous memory addresses, the CPU caches the array into the ultra-fast L1/L2 hardware cache. Merge Sort constantly creates new disjoint arrays in RAM, triggering massive cache misses. In hardware reality, Quick Sort’s raw execution speed completely dominates Merge Sort, making it practically faster in 99% of scenarios.