From the author of
- Does the Java system sort use one of these methods for String sorts?
- No, but the standard implementation includes a fast string compare that makes standard sorts competitive with the methods considered here.
- So, I should just use the system sort for String keys?
- Probably yes in Java, though if you have huge numbers of strings or need an exceptionally fast sort, you may wish to switch to char arrays instead of String values and use a radix sort.
- What is explanation of the log2 N factors on the table in the previous page?
- They reflect the idea that most of the comparisons for these algorithms wind up being between keys with a common prefix of length log N. Recent research has established this fact for random strings with careful mathematical analysis (see booksite for reference).