THE SUBJECT OF this chapter is the sorting algorithm that is probably used more widely than any other, quicksort . The basic algorithm was invented in 1960 by C. A. R. Hoare, and it has been studied by many people since that time (see reference section). Quicksort is popular because it is not difficult to implement, works well for a variety of different kinds of input data, and consumes fewer resources than any other sorting method in many situations.
The quicksort algorithm has the desirable features that it is in place (uses only a small auxiliary stack), requires time only proportional to
N log N on the average to sort
N items, and has an extremely short inner loop. Its drawbacks are that it is not stable, takes about ...