- Key-indexed counting
- LSD string sort
- MSD string sort
- Three-way string quicksort
- Which string-sorting algorithm should I use?
- Q&A
- Exercises
- CREATIVE PROBLEMS
- EXPERIMENTS
Like this article? We recommend
Like this article? We recommend
Like this article? We recommend
Which string-sorting algorithm should I use?
Naturally, we are interested in how the string-sorting methods that we have considered compare to the general-purpose methods that we considered in Chapter 2. The following table summarizes the important characteristics of the string-sort algorithms that we have discussed in this section (the rows for quicksort, mergesort, and 3-way quicksort are included from Chapter 2, for comparison).
|
algorithm |
stable? |
inplace? |
order of growth of |
sweet spot |
|
|
running time |
extra space |
||||
|
insertion sort for strings |
yes |
yes |
between N and N2 |
1 |
small arrays, arrays in order |
|
quicksort |
no |
yes |
N log 2 N |
log N |
general-purpose when space is tight |
|
mergesort |
yes |
no |
N log2 N |
N |
general-purpose stable sort |
|
3-way quicksort |
no |
yes |
between N and N log2 N |
log N |
large numbers of equal keys |
|
LSD string sort |
yes |
no |
NW |
N |
short fixed-length strings |
|
MSD string sort |
yes |
no |
between N and Nw |
N + WR |
random strings |
|
3-way string quicksort |
no |
yes |
between N and Nwlog R |
W + log N |
general-purpose, strings with long prefix matches |
Performance characteristics of string-sorting algorithms
As in Chapter 2, multiplying these growth rates by appropriate algorithm- and data-dependent constants gives an effective way to predict running time.
As explored in the examples that we have already considered and in many other examples in the exercises, different specific situations call for different methods, with appropriate parameter settings. In the hands of an expert (maybe that’s you, by now), dramatic savings can be realized for certain situations.