Quicksort

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