Quick sort is an efficient in-place sorting algorithm. It’s a divide and conquer algorithm that works by selecting a ’pivot’ element from an array and partitioning the other elements into two sub-arrays according to whether they are less than or greater than the pivot. The sub-arrays are then recursively sorted.
Time Complexity:
In the best case (which occurs when the pivot element is always the median), the partitioning steps will result in subarrays of equal size (or nearly equal), achieving a balanced recursion tree. In this case, the time complexity is O(n log n), where n is the number of elements in the array.
The worst-case scenario occurs when the pivot is either the smallest or largest element in the array, which leads to a highly unbalanced partition and a worst-case time complexity of O(n2).
The average case time complexity of quicksort is also O(n log n), but it tends to be faster in practice than other O(n log n) algorithms, because its inner loop can be efficiently implemented on most architectures, and in most real-world data, it performs significantly better than other divide-and-conquer methods.
Space Complexity:
Quick sort is an in-place sorting algorithm but needs stack space for recursion. Specifically, a quicksort can operate in O(log n) space.
To sum up, these are the time complexities under different scenarios:
- Worst-case performance: O(n2)
- Best-case performance: O(nlog n)
- Average performance: O(nlog n)
- Worst-case space complexity: O(n) auxiliary (naive) or O(log n) auxiliary (Sedgewick 1978)