Chapter Seven. Quicksort

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’s desirable features are 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 ...

Get Algorithms in Java, Third Edition, Parts 1-4 now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.