Burstsort

Burstsort i njegove varijante su algoritmi koje služe za efikasno sortiranje niski u keš memoriji. Burstsort je brži od quicksorta kada su u pitanju velike grupe podataka. Burstsort algoritam koristi drvo za skladištenje prefiksnih niski, sa dinamičnim poretkom pokazivača kao krajnjih čvorova koji sadrže sortirane, jedinstvene sufikse (poznatiji kako segmenti). Neke verzije kopiraju krajeve niski u segmente. Burstsort je dobio ime tako što segmenti rastu preko predodređenog praga i onda u jednom trenutku „pucaju“. Novija verzija koristi segment registre sa manjim sub-segmentima da bi smanjili upotrebu memorije. Multikey quicksort, ekstenzija osnovnog trosmernog quicksorta je zadužen za raspoređivanje sadržaja segmeta u najvećem broju implementacija. Deljenjem unosa segmenta sa zajedničkim prefiksima, raspoređivanje može biti efektivno uređeno u keš memoriji.

Literatura

• The original burstsort article: Cache-Conscious Sorting of Large Sets of Strings with Dynamic Tries
• A burstsort derivative (C-burstsort), faster than burstsort: Cache-Efficient String Sorting Using Copying
• The data type used in burstsort: Burst Tries: A Fast, Efficient Data Structure for String Keys
• Efficient Trie-Based Sorting of Large Sets of Strings
• Engineering Burstsort: Towards Fast In-Place String Sorting
• A burstsort implementation in C++: Free C++ Copy-Burstsort Library
• A burstsort implementation in Java: burstsort4j
• Judy arrays are a type of copy burstsort: C implementation