Quicksort
Quicksort picks a pivot value, partitions the range so every smaller value ends up to its left and every larger value to its right, then recursively sorts each side. This implementation uses the Lomuto partition scheme, always choosing the last element of each range as the pivot.
When it is the right choice
Quicksort is usually the fastest general-purpose comparison sort in practice, and it partitions in place, needing only O(log n) auxiliary space for its recursion. Its worst case is O(n²), and this fixed last-element pivot rule makes that worst case easy to trigger deliberately: an already-sorted or reverse-sorted array. Production implementations avoid this by choosing a random or median-of-three pivot instead of a fixed one, for exactly this reason.
How it works
- If the range holds more than one value, choose its last value as the pivot.
- Compare every other value in the range with the pivot.
- Whenever a value is smaller than the pivot, swap it next to the growing group of smaller values.
- Once every value has been checked, swap the pivot into place between the smaller and larger groups — this is now the pivot's final sorted position.
- Recursively sort the values smaller than the pivot, then recursively sort the values larger than the pivot.
Worth noticing
- It is not stable: partitioning can swap an equal element past another equal element.
- Its worst case, O(n²), happens on input that is already sorted or reverse-sorted with this last-element pivot rule — exactly the input a student is most likely to try first.
- Unlike merge sort, it sorts in place: no auxiliary array is needed for the partitioning itself, only the recursion stack.
Cost
- Best
- O(n log n)
- Average
- O(n log n)
- Worst
- O(n²)
- Extra space
- O(log n)
- Stable
- No