⚡ Quick Sort Fundamentals

🎯 What is Quick Sort?

Quick Sort is an efficient, in-place, divide-and-conquer sorting algorithm developed by Tony Hoare in 1959. It works by selecting a 'pivot' element and partitioning the array around it — elements smaller than the pivot go to the left, larger to the right — then recursively sorting the subarrays.

Time: O(n log n) avg | O(n²) worst | Space: O(log n) | Stable: ❌

Deep Explanation

Why Quick Sort is so fast: In practice, Quick Sort outperforms Merge Sort and Heap Sort because it has good cache locality (in-place partitioning) and low constant factors. It's the default sorting algorithm in many standard libraries (though many now use hybrid Introsort to avoid worst-case behavior).

Key Insight: The partition operation places the pivot in its final sorted position. After partitioning, the pivot never moves again — this is the key to Quick Sort's efficiency.

📌 In-Place Sorting📌 Divide & Conquer📌 Cache Friendly📌 Unstable

def quick_sort(arr, low=0, high=None):
    if high is None:
        high = len(arr) - 1
    if low < high:
        pivot_index = partition_lomuto(arr, low, high)
        quick_sort(arr, low, pivot_index - 1)
        quick_sort(arr, pivot_index + 1, high)
    return arr

def partition_lomuto(arr, low, high):
    pivot = arr[high]  # Choose last element as pivot
    i = low - 1
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

print(quick_sort([10, 7, 8, 9, 1, 5]))
# Output: [1, 5, 7, 8, 9, 10]

📐 Partition & Conquer Walkthrough

🎯 Example: [10, 7, 8, 9, 1, 5] with pivot=5

Partition: Rearrange so that elements < 5 come before, > 5 after. Result: [1, 5, 8, 9, 10, 7] with pivot at index 1
Recursively sort left: [1] (base case)
Recursively sort right: [8, 9, 10, 7] with pivot=7 → [7, 8, 9, 10]
Final: [1, 5, 7, 8, 9, 10]

Visual Breakdown

Quick Sort works by selecting a pivot and creating two partitions. The pivot ends up exactly where it should be in the final sorted array. The algorithm then recursively sorts the left and right partitions independently.

⏱️ Time & Space Complexity

🎯 Complexity Analysis

Best-case (O(n log n)): Pivot always divides array into equal halves
Worst-case (O(n²)): Pivot is always smallest or largest (already sorted or reverse sorted with bad pivot)
Average-case (O(n log n)): Random pivot gives good expected performance
Space Complexity: O(log n) for recursion stack (average); O(n) worst-case for recursion depth

Recurrence Relation

Best/Average: T(n) = 2T(n/2) + O(n) = O(n log n)
Worst-case: T(n) = T(n-1) + O(n) = O(n²)

🔀 Partition Schemes (Lomuto vs Hoare)

🎯 Two Classic Approaches

Lomuto Partition: Simpler to understand, uses single loop, but does more swaps. Pivot ends at the boundary.
Hoare Partition: Original scheme by Tony Hoare. Uses two pointers moving toward each other. Generally performs fewer swaps and is more efficient.

def partition_hoare(arr, low, high):
    pivot = arr[low]  # Choose first element as pivot
    i, j = low - 1, high + 1
    while True:
        i += 1
        while arr[i] < pivot:
            i += 1
        j -= 1
        while arr[j] > pivot:
            j -= 1
        if i >= j:
            return j
        arr[i], arr[j] = arr[j], arr[i]

def quick_sort_hoare(arr, low, high):
    if low < high:
        p = partition_hoare(arr, low, high)
        quick_sort_hoare(arr, low, p)
        quick_sort_hoare(arr, p + 1, high)
    return arr

💻 Multiple Implementations

# Functional style (creates new arrays - not in-place)
def quick_sort_functional(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[-1]
    left = [x for x in arr[:-1] if x <= pivot]
    right = [x for x in arr[:-1] if x > pivot]
    return quick_sort_functional(left) + [pivot] + quick_sort_functional(right)

# In-place with random pivot for better average performance
import random

def quick_sort_random(arr, low, high):
    if low < high:
        random_idx = random.randint(low, high)
        arr[random_idx], arr[high] = arr[high], arr[random_idx]
        pi = partition_lomuto(arr, low, high)
        quick_sort_random(arr, low, pi - 1)
        quick_sort_random(arr, pi + 1, high)
    return arr

🎯 Pivot Selection Strategies

First/Last Element: Simple but O(n²) on sorted data
Random Pivot: Makes worst-case extremely unlikely (expected O(n log n))
Median-of-Three: Takes median of first, middle, last — avoids worst-case for sorted arrays
Median-of-Medians: Guarantees O(n log n) worst-case (BFPRT algorithm)

def median_of_three(arr, low, high):
    mid = (low + high) // 2
    candidates = [(arr[low], low), (arr[mid], mid), (arr[high], high)]
    candidates.sort()
    median_idx = candidates[1][1]
    arr[median_idx], arr[high] = arr[high], arr[median_idx]
    return partition_lomuto(arr, low, high)

📊 Step-by-Step Visualization

🎯 Example: [3, 6, 8, 10, 1, 2, 1] (Pivot = last element)

Initial: [3, 6, 8, 10, 1, 2, 1] — pivot=1 (last)
Partition: All elements < 1? none. Move pivot to front: [1, 6, 8, 10, 1, 2, 3]
Recursive on right: [6, 8, 10, 1, 2, 3] pivot=3 → partition → [1, 2, 3, 10, 8, 6]
Continue until sorted: [1, 1, 2, 3, 6, 8, 10]

🛡️ Stability & Properties

🎯 Quick Sort is NOT Stable

Quick Sort is an unstable sorting algorithm because the partition step swaps non-adjacent elements, potentially changing the relative order of equal elements. To make it stable, you would need to use a stable partition (which would lose in-place property).

When Stability Matters

If stability is required, use Merge Sort or Timsort instead. However, for many applications where stability isn't needed, Quick Sort's speed makes it preferable.

📈 Comparison with Other Sorts

vs Merge Sort: Quick Sort is in-place and has better cache locality (faster in practice); Merge Sort is stable and has guaranteed O(n log n)
vs Heap Sort: Both in-place, but Quick Sort is typically 2-3x faster due to locality
vs Insertion Sort: Insertion sort is faster for very small arrays (n < 15-20)
Python's Timsort: Hybrid of Merge + Insertion, not Quick Sort
Java's Arrays.sort(): Uses Dual-Pivot Quick Sort for primitives

⚡ Optimizations & Hybrid Approaches

Introsort: Hybrid of Quick Sort, Heap Sort, and Insertion Sort. Starts with Quick Sort, switches to Heap Sort if recursion depth exceeds O(log n). Used in C++'s std::sort.
Insertion Sort for Small Subarrays: When subarray size < 15-20, insertion sort is faster due to lower overhead.
Tail Call Optimization: Recursively sort the smaller partition first to reduce stack depth to O(log n).

def introsort(arr, low, high, depth_limit):
    if high - low <= 16:
        insertion_sort_range(arr, low, high)
        return
    if depth_limit == 0:
        heap_sort_range(arr, low, high)
        return
    pivot = partition_lomuto(arr, low, high)
    introsort(arr, low, pivot - 1, depth_limit - 1)
    introsort(arr, pivot + 1, high, depth_limit - 1)

def insertion_sort_range(arr, low, high):
    for i in range(low + 1, high + 1):
        key = arr[i]
        j = i - 1
        while j >= low and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

🔄 Iterative (Stack-Based) Quick Sort

🎯 Avoiding Recursion

Use an explicit stack to simulate recursion. This eliminates recursion depth limits and can be more memory-efficient.

def iterative_quick_sort(arr):
    stack = [(0, len(arr) - 1)]
    while stack:
        low, high = stack.pop()
        if low < high:
            pivot = partition_lomuto(arr, low, high)
            # Push larger partition first for better stack efficiency
            if pivot - low > high - pivot:
                stack.append((low, pivot - 1))
                stack.append((pivot + 1, high))
            else:
                stack.append((pivot + 1, high))
                stack.append((low, pivot - 1))
    return arr

🚀 Parallel & Multi-Pivot Quick Sort

🎯 Leveraging Concurrency

Quick Sort's divide-and-conquer nature makes it highly parallelizable. After partitioning, the two subarrays can be sorted independently in parallel.

from concurrent.futures import ThreadPoolExecutor
import threading

def parallel_quick_sort(arr, low, high, depth=0, max_depth=4):
    if low < high:
        if depth >= max_depth:
            quick_sort(arr, low, high)
            return
        pivot = partition_lomuto(arr, low, high)
        with ThreadPoolExecutor(max_workers=2) as executor:
            left_future = executor.submit(parallel_quick_sort, arr, low, pivot-1, depth+1, max_depth)
            right_future = executor.submit(parallel_quick_sort, arr, pivot+1, high, depth+1, max_depth)
            left_future.result()
            right_future.result()
    return arr

🔀 Dual-Pivot Quick Sort (Java's Algorithm)

🎯 Two Pivots for Better Performance

Introduced by Vladimir Yaroslavskiy, this variant uses two pivots, dividing the array into three partitions. It's the default sorting algorithm for primitives in Java's Arrays.sort().

def dual_pivot_quick_sort(arr, low, high):
    if low < high:
        if arr[low] > arr[high]:
            arr[low], arr[high] = arr[high], arr[low]
        p, q = arr[low], arr[high]
        l, m, r = low + 1, low + 1, high - 1
        while m <= r:
            if arr[m] < p:
                arr[m], arr[l] = arr[l], arr[m]
                l += 1
                m += 1
            elif arr[m] >= q:
                while arr[r] > q and m < r:
                    r -= 1
                arr[m], arr[r] = arr[r], arr[m]
                r -= 1
                if arr[m] < p:
                    arr[m], arr[l] = arr[l], arr[m]
                    l += 1
                m += 1
            else:
                m += 1
        l -= 1
        r += 1
        arr[low], arr[l] = arr[l], arr[low]
        arr[high], arr[r] = arr[r], arr[high]
        dual_pivot_quick_sort(arr, low, l - 1)
        dual_pivot_quick_sort(arr, l + 1, r - 1)
        dual_pivot_quick_sort(arr, r + 1, high)
    return arr

💪 Practice & Problem Patterns

🎯 Common Quick Sort Based Problems

Quick Select (K-th Smallest Element): Use partition to find the k-th smallest in O(n) average time
Dutch National Flag (3-way partition): Partition array into three colors (0,1,2)
Sort Colors (LeetCode 75): Direct application of 3-way partition
K Closest Points to Origin: Use quick select for O(n) average
Top K Frequent Elements: Quick select on frequency counts
Find the Median: Quick select gives O(n) expected time

def quick_select(arr, low, high, k):
    """Find k-th smallest element (0-indexed)"""
    if low <= high:
        pivot_index = partition_lomuto(arr, low, high)
        if pivot_index == k:
            return arr[pivot_index]
        elif pivot_index > k:
            return quick_select(arr, low, pivot_index - 1, k)
        else:
            return quick_select(arr, pivot_index + 1, high, k)
    return None

def kth_smallest(arr, k):
    import random
    arr_copy = arr.copy()
    return quick_select(arr_copy, 0, len(arr_copy) - 1, k)

print(kth_smallest([7, 10, 4, 3, 20, 15], 3))  # 3rd smallest = 10?