Efficient String Sorting Algorithms: Cache-aware and Cache-Oblivious
R. Angrish1, D. Garg2
1Ritika Angrish, Department of Computer Science, Thapar University, Patiala, India.
2Deepak Garg, Department of Computer Science, Thapar University, Patiala, India.
Manuscript received on April 19, 2011. | Revised Manuscript received on April 29, 2011. | Manuscript published on May 05, 2011. | PP: 12-16 | Volume-1 Issue-2, May 2011. | Retrieval Number: A022031211
Open Access | Ethics and Policies | Cite | Mendeley
© The Authors. Published By: Blue Eyes Intelligence Engineering and Sciences Publication (BEIESP). This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/)
Abstract: 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 our 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. The various algorithms discussed are: CRadix Sort, Burstsort and cache-oblivious string sorting algorithm. The improvement in CRadix Sort is achieved by starting the sorting with the most significant digit and associating a small block of main memory called the key buffer to each key and sorting a portion of each key into its corresponding key buffer. Burstsort is a trie-based string sorting algorithm that distributes strings into small buckets whose contents are then sorted in cache. The cache-oblivious string sorting algorithm is a randomized algorithm for string sorting which uses signature technique (reduces the sequence by creating a set of “signatures” strings having the same trie structure as the original set) to sort strings.).
Keywords: Cache-aware, Cache-oblivious, External string sorting.