Efficient String Sorting Algorithms: Cache-Aware and Cache-Oblivious

Date Added: May 2011
Format: PDF

Sorting is a process of rearranging a sequence of objects into some kind of predefined linear order. String data is very common and most occurring data type. Sorting a string involves comparison it character by character which is more time consuming than integer sorting. Also, sorting forms the basis of many applications like data processing, databases, pattern matching and searching etc. So implementing improvements to make it fast and efficient will help in reducing the computational time and thus making the authors' applications run faster. This paper briefs about various fast and efficient string sorting algorithms. The algorithms have been divided into two categories: cache-aware and cache-oblivious.