Home > Articles > Programming > Algorithms

  • Print
  • + Share This
From the author of Which string-sorting algorithm should I use? 

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
typical number calls to charAt()
to sort N strings
from an R-character alphabet
(average length w, max length W)

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.

  • + Share This
  • 🔖 Save To Your Account