Basic Algorithms — Quicksort

Sorting an array with randomly selected pivots

I introduced a sorting algorithm called Merge-Sort in a previous article and continue writing about another sorting algorithm, Quicksort, in this post. The expected cost of Quicksort is Θ(nlgn), while the worst case that costs Θ(n²) would materialize only at a probability of 2/n!. I will show later in the performance comparison that the constant hidden in Θ notation is lower in Quicksort thus the algorithm outperforms Merge-Sort whose cost is same Θ(nlgn).