Quick sort

The simple version of quicksort uses $O(n)$ extra storage space. The in-place version of quicksort uses $O(\log n)$ extra space. The in-place version of the algorithm uses partition which partitions a subrange of an array so that elements less than the pivot are before it and elements greater than the pivot are after it.