7. Advanced Sorting

In This Chapter

Shellsort

Partitioning

Quicksort

Radix Sort

Timsort

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 ...

Get Data Structures & Algorithms in Python now with the O’Reilly learning platform.

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