7. Advanced Sorting
In This Chapter
We started discussing sorting in the aptly titled Chapter 3, “Simple Sorting.” The sorts described there—the bubble, selection, and insertion sorts—are easy to implement but 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 in detail: Shellsort and quicksort. These sorts both operate much faster than the simple sorts: the Shellsort in about O(N×(log N)2) time, and quicksort in O(N×log N) time. Neither of these sorts requires a large amount of extra ...