Time ComplexityLesson 48Free preview
Quick Sort
This lesson is part of DSA · All levels
Summary
Quick sort grows O(n log n) on average because the partition divides the data into two parts that are balanced with depths around log n. The worst case scenario is when the pivot always divides very unevenly, for example on data sorted by the pivot end. Its space complexity in-place is small, only O(log n) for the average recursion stack.
Key points
- Average with a balanced partition
- The worst case of partition is highly unbalanced
- Average depth of recursion
- Space complexity in-place for the average recursion stack
Full lesson
Code examples and quizzes
Full lessons, code examples, and quizzes are available to subscribers. 5 questions.