7. Advanced Sorting

In This Chapter




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)2) time, and quicksort in O(N*logN) time. Neither of these sorts requires a large amount of extra space, as mergesort ...

Get Data Structures and Algorithms in Java, 2nd Edition now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.