Cubesort

Cubesort is a parallel sorting algorithm that builds a self-balancing multi-dimensional array from the keys to be sorted. Because the axes of the array are kept at similar lengths, the structure resembles a cube, and after each key is inserted the cube can be quickly converted back into an ordinary sorted array. To find where a new element belongs, it uses a specialized binary search along each axis, and when an axis grows too long it is split. Locality of reference is described as optimal because only four binary searches on small arrays are needed for each insertion, and the high cost of inserting into one single large array is avoided by using many small dynamic arrays instead. A cubesort implementation written in C was published in 2014. The article is short and states no running time for the method.