QuickSort

QuickSort is a comparison-based, divide-and-conquer sorting algorithm that operates in-place with O(n log n) average-case time complexity. It works by selecting a pivot element and partitioning the array into elements less than, equal to, and greater than the pivot.

Key Characteristics

• Average Complexity: O(n log n)
• Worst-Case Complexity: O(n²) (mitigated via pivot optimization)
• Space Complexity: O(log n) stack space (in-place implementation)
• Stability: Not stable by default
• Preferred For: Large datasets, memory-constrained environments

Algorithm Steps

1. Partitioning Scheme (Lomuto)

Java

int partition(int[] arr, int low, int high) {
    int pivot = arr[high]; 
    int i = low - 1;

    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(arr, i, j);
        }
    }
    swap(arr, i + 1, high);
    return i + 1;
}

2. Recursive Implementation

Java

void quickSort(int[] arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

Complexity Analysis

Case	Time Complexity	Space Complexity
Best	O(n log n)	O(log n)
Average	O(n log n)	O(log n)
Worst	O(n²)	O(n)
Parallel	O(n)	O(n)

Pivot Selection Strategies

Strategy	Description	Pros/Cons
Last Element	Simple implementation	Prone to worst-case behavior
Median-of-Three	Median of first/middle/last elements	Better performance on sorted data
Random	Random element selection	Probabilistic O(n log n) guarantee
Hybrid (Introsort)	Switch to HeapSort at depth limit	Avoids O(n²) worst-case

Optimization Techniques

1. Tail Recursion Elimination

Java

void quickSortOptimized(int[] arr, int low, int high) {
    while (low < high) {
        int pi = partition(arr, low, high);
        quickSortOptimized(arr, low, pi - 1);
        low = pi + 1;
    }
}

2. InsertionSort Hybrid

Java

void hybridSort(int[] arr, int low, int high) {
    if (high - low < 16) {
        insertionSort(arr, low, high);
    } else {
        int pi = partition(arr, low, high);
        hybridSort(arr, low, pi - 1);
        hybridSort(arr, pi + 1, high);
    }
}

Best Practices

1. Pivot Choice: Use randomized pivot or median-of-three for real-world data
2. Stack Management: Implement iterative version for large datasets
3. Fallback Strategy: Combine with InsertionSort for small partitions (n < 16)
4. Duplicate Handling: Use three-way partitioning for datasets with many duplicates
5. Stability: Implement with O(n) extra space if stability required

Comparison with Other Algorithms

Algorithm	Average Time	Worst Time	Space	Stable	Adaptivity
QuickSort	O(n log n)	O(n²)	O(log n)	No	Yes
MergeSort	O(n log n)	O(n log n)	O(n)	Yes	No
HeapSort	O(n log n)	O(n log n)	O(1)	No	No
TimSort	O(n log n)	O(n log n)	O(n)	Yes	Yes

Implementation Notes

• Use Arrays.sort() in Java (which uses Dual-Pivot QuickSort)
• For object arrays, Java uses modified MergeSort (stable)
• Parallel implementations use ForkJoinPool framework