Quick Sort
- Ω( n log n )
- Θ( n log n )
- O( n2 )
- space O( log n )
- Comparisons count only element-against-element checks; loop and index checks are never counted.
- Reads and writes include reads and writes to helper buffers (merge, counting, radix, bucket and tim sort).
- A swap counts once, as a swap. It is never also counted as a read or a write.
- Real time is the average time of the counted sort on this device over repeated runs, measured once before playback and independent of animation speed. Visual time is the time spent animating, excluding pauses.
How quick sort works
Quick sort is a comparison sort that is efficient on average. It is a divide and conquer algorithm that works by selecting a pivot element from the 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 sorted recursively. This can be done in-place, requiring small additional amounts of memory to perform the sorting.
Read more
There are many different versions of quicksort that pick pivot in different ways. The choice of pivot can make a big difference in the performance of quicksort. This version takes the median of the first, middle and last element, which keeps sorted and reversed input fast.
| Best time | Ω( n log n ) | good |
|---|---|---|
| Average time | Θ( n log n ) | good |
| Worst time | O( n2 ) | poor |
| Worst space | O( log n ) | good |
Big O notation gives the lower, average and upper bounds of an algorithm. Time complexity bounds the number of operations; space complexity bounds the extra memory it uses.