a best-case O(n log n) algorithm that has a lower space complexity (in-place sort), and is more suitable for sorting large datasets

solution:

1. choose an item to be the pivot
2. move all elements < pivot to the left, and all elements > pivot to the right — ‘partitioning’
3. perform a swap such that the pivot is now in the middle
4. recursively repeat on each half… until everything is sorted

note: quicksort can also be implemented iteratively using a stack

the ‘partitioning’ step

1. have a index/pointer $i$ and $j$ point at the lo and hi respectively
2. so long as $i$ < pivot and $j$ > pivot, move them towards each other
3. if one fails to satisfy the condition, keep moving the other one until both fail, then swap (thus fixing both of their positions)
4. repeat steps 2-3 until $i$ and $j$ point to the same index

❗quicksort is not stable, but it can be if the implementation is changed (but uses more memory)

• quicksort C code