Sorting Strings
Paolo Ferragina · Cambridge University Press eBooks · 2023
This chapter discusses the limitations incurred by the sorters of atomic items when applied to sort variable-length items (aka strings). It then introduces a simple, yet effective comparison-based lower bound, which is eventually matched by means of an elegant variant of QuickSort, named Multi-key QuickSort, properly designed to deal with strings. The structure of this string sorter will also allow us to introduce an interesting, powerful, and dynamic data structure for string indexing, the ternary search tree, which supports efficient prefix searches over a dynamic string dictionary that fits in the internal memory of a computer. The case of large string dictionaries that cannot be fit into the internal memory of a computer is discussed in Chapter 9.