Sorting and Searching Strings

We present theoretical algorithms for sorting and searching multidimensional data and practical C implementations for the application where keys are character strings. The sorting algorithm, an amalgam of Quicksort and radix sort, is competitive with the best known C sort codes. The searching algorithm, an amalgam of trees and binary search trees, is faster than hashing and other commonly used search methods. The basic ideas behind the algorithms date back at least to the 1960s, but their practical utility has been overlooked. Analytic results and extensions to more difficult string processing problems are also included.