Quick Sort - Complexity & Optimizations

Complexity Analysis

Quick sort has excellent average performance but can degrade in worst case.

Time Complexity

Average Case: O(n log n)

• Good pivot selection splits array roughly in half
• Each level does O(n) work
• O(log n) levels

Best Case: O(n log n)

• Pivot always splits array in half
• Balanced partitions

Worst Case: O(n²)

• Pivot is always smallest or largest
• Unbalanced partitions (like sorted array with last-element pivot)
• Rare with good pivot selection

Space Complexity

O(log n) - Logarithmic Space

• Recursion stack depth
• O(log n) in average case
• O(n) in worst case (unbalanced)

Why O(n log n) Average?

• Partition: O(n) work per level
• Levels: O(log n) levels on average
• Total: O(n) × O(log n) = O(n log n)

Comparison with Other Algorithms

Optimizations

1. Random pivot: Choose random element as pivot
2. Median of three: Use median of first, middle, last
3. Insertion sort: Use for small sub-arrays (n < 10)
4. Three-way partition: Handle duplicates efficiently

When to Use

Quick sort is ideal when:

• You need fast average performance
• Memory is limited
• Stability isn’t required
• You can handle worst-case risk

What’s Next?

Let’s test your understanding with practice problems and a quiz.