Pick a pivot and partition the array so smaller values sit to its left and the rest to its right. The pivot is then in its final place, and each side is sorted the same way. This version (Lomuto partition) uses the last element as the pivot.
- Average time
- O(n log n)
- Space
- O(log n)