Quicksort

worst-case running time of n² on an input array of n numbers.
Despite this slow worst-case running time, quicksort is often the best
practical choice for sorting because it is remarkably efficient on the average:

1. expected running time is nlgn
2. the constant factors hidden in the nlgn notation are quite small.
3. It also has the advantage of sorting in place, and it works well even in virtual-memory environments.