The performance of quicksort
There are a lot of implementations of quick sort algorithm. Even though the time complexity of the algorithm is nlog(n), the real performance is highly depending on the partition algorithm.
The pseudo code of quicksort algorithm is as follows.
Two partition algorithms
There are two famous partition algorithms. As my experience, Lumuto-Partition is better for performance and readibility.
Hoare-Partition algorithm is not so good to understand due to several duplicated loops.
The pseudo code of Hoare-partition algorithm:
The pseudo code of Lumuto-partition algorithm:
The following source code presents the Lumuto-Partition implementation. This is very fast. Morover, the code is intuitive and easy to understand.