Cubesort
Lua error in package.lua at line 80: module 'strict' not found. Lua error in package.lua at line 80: module 'strict' not found.
Lua error in Module:Infobox at line 199: malformed pattern (missing ']').
Cubesort is a parallel sorting algorithm that builds a self-balancing multi-dimensional array from the keys to be sorted. As the axes are of similar length the structure resembles a cube. After each key is inserted the cube can be rapidly converted to an array.[1]
A cubesort implementation written in C was published in 2014.[2]
Operation
Cubesort's algorithm uses a specialized binary search on each axis to find the location to insert an element. When an axis grows too large it is split. Locality of reference is optimal as only 4 binary searches are performed on small arrays for each insertion. By using many small dynamic arrays the high cost for insertion on single large arrays is avoided.
References
<templatestyles src="Reflist/styles.css" />
Cite error: Invalid <references> tag; parameter "group" is allowed only.
<references />, or <references group="..." />External links
- Cubesort description and implementation in C
- Algorithms and Computation: 7th International Symposium, ISAAC '96, Osaka ... edited by Tetsuo Asano et al, pp 187-188, http://books.google.com/books?id=vilOl8JCpFUC&pg=PA188&lpg=PA188&hl=en&f=false (passing mention)
<templatestyles src="Asbox/styles.css"></templatestyles>
 |
This algorithms or data structures-related article is a stub. You can help Wikipedia by expanding it. |
