Naive vs Lomuto vs Hoare Quicksort Partition

Naive
- Stable
- Requires 3 traversals

Lomuto
- Unstable
- In-place
- Faster than Naive
- Slower for larger data sets >100000. This is because the Naive solution does not swap elements in-place. Lomuto's memory reduction naturally leads to cases where larger runtimes are expected.

Hoare
- Unstable
- In-place
- Faster than Lomuto
- Used in practice

Note stable algorithms retain the original order of equal elements in the output array
Ex: Sort [[1,5], [1,2], [5,4], [3,4], [7,9]] on first key
A stable sorting algorithm will sort the list as: [[1,5], [1,2], [3,4], [5,4], [7,9]]
While an unstable sorting algorithm MAY sort the list as: [[1,2], [1,5], [3,4], [5,4], [7,9]]

Sources
- https://www.geeksforgeeks.org/quick-sort/
- https://www.geeksforgeeks.org/hoares-vs-lomuto-partition-scheme-quicksort/