Data Structures and Algorithms in Java, 2nd Edition

7. Advanced Sorting

In This Chapter

• Shellsort

• Partitioning

• Quicksort

• Radix Sort

We discussed simple sorting in the aptly titled Chapter 3, “Simple Sorting.” The sorts described there—the bubble, selection, and insertion sorts—are easy to implement but are rather slow. In Chapter 6, “Recursion,” we described the mergesort. It runs much faster than the simple sorts but requires twice as much space as the original array; this is often a serious drawback.

This chapter covers two advanced approaches to sorting: Shellsort and quicksort. These sorts both operate much faster than the simple sorts: the Shellsort in about O(N*(logN)²) time, and quicksort in O(N*logN) time. Neither of these sorts requires a large amount of extra space, as mergesort ...