# Quicksort

2018-04-21

Algorithm

2023

Time Complexity
With partition, the elements compared each time are as follow:
n, n/2, n/2, n/4, n/4, n/4, n/4, ..., 1, 1, ..., 1 (n ones)
And their sum is:
n, n, n, ..., n
But how much n?
Since n is divided to 1 by 2, there sure is log2(n) number of n.
So the time complexity is: n*log2(n)
Unique-elements sorting implement
From Quicksort - wikipedia:
algorithm quicksort(A, lo, hi) is
if lo < hi then
p := partition(A, lo, hi)
quicksort(A, lo, p)
quicksort(A, p + 1, hi)
algorithm partition(A, lo, hi) is
pivot := A[lo]
i := lo - 1
j := hi + 1
loop