A quick sort is an efficient sorting algorithm that uses a recursive divide-and-conquer algorithm.
- An item in the list (called the pivot) is picked
- Smaller values are moved before the pivot (left), and greater items after (right). This is called the partition operation.
- Recursively apply the above steps to the left and right lists.
Using a random index or a median of three approach for the pivot ensures worst case behaviour on already sorted arrays is avoided.
🔔 Complexity is considered in terms of worst case.
| Notes | |
|---|---|
| Θ(n log n) |
| Notes | |
|---|---|
| Θ(n log n) | The in-place version of quick sort |
| Θ(n) | In this naive implementation three temporary lists are created and concatenated recursively |