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
**Advantages:**
• O(n log n) average
• Fast in practice
• In-place (O(log n) space)
• Good cache performance
**Disadvantages:**
• O(n²) worst case
• Not stable
• Performance depends on pivot
**Advantages:**
• Guaranteed O(n log n)
• Stable algorithm
• Predictable performance
**Disadvantages:**
• O(n) extra space
• Not in-place
• More memory overhead
**Advantages:**
• Guaranteed O(n log n)
• In-place (O(1) space)
• No worst case
**Disadvantages:**
• Not stable
• Slower constants
• More complex
Optimizations
- Random pivot: Choose random element as pivot
- Median of three: Use median of first, middle, last
- Insertion sort: Use for small sub-arrays (n < 10)
- 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.
Progress 86%
Page 6 of 7
← Previous
→ Next