Fast algorithms for sorting and searching strings

Jon L. Bentley, Robert Sedgewick

Research output: Contribution to conferencePaper

236 Scopus citations

Abstract

We present theoretical algorithms for sorting and searching multikey data, and derive from them practical C implementations for applications in which keys are character strings. The sorting algorithm blends Quicksort and radix sort; it is competitive with the best known C sort codes. The searching algorithm blends tries and binary search trees; it 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. We also present extensions to more complex string problems, such as partial-match searching.

Original languageEnglish (US)
Pages360-369
Number of pages10
StatePublished - Jan 1 1997
Externally publishedYes
EventProceedings of the 1996 8th Annual ACM-SIAM Symposium on Discrete Algorithms - New Orleans, LA, USA
Duration: Jan 5 1997Jan 7 1997

Other

OtherProceedings of the 1996 8th Annual ACM-SIAM Symposium on Discrete Algorithms
CityNew Orleans, LA, USA
Period1/5/971/7/97

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Fast algorithms for sorting and searching strings'. Together they form a unique fingerprint.

  • Cite this

    Bentley, J. L., & Sedgewick, R. (1997). Fast algorithms for sorting and searching strings. 360-369. Paper presented at Proceedings of the 1996 8th Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, LA, USA, .