worst-case running time of n2 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:
- expected running time is nlgn
- the constant factors hidden in the nlgn notation are quite small.
- It also has the advantage of sorting in place, and it works well even in virtual-memory environments.
