Cubesort

Cubesort is a parallel comparison sort that maintains a cube-shaped index of sorted runs and merges them adaptively. It is rarely seen in everyday code; the closest practical Python equivalent is sortedcontainers.SortedList, which keeps a list-of-lists and supports O(log n) insertion plus near-linear-time bulk reads.

Complexity

How it works

Conceptually: organize sorted runs into a hierarchical structure (a "cube") that allows O(log n) insertion and adaptive merging. Best case O(n) on already-sorted input, average and worst O(n log n). It was designed for parallel hardware and competes with Timsort on partially-sorted inputs.

Python implementation

# Cubesort itself is rarely implemented in Python. The closest
# practical equivalent is SortedList, which maintains sorted order
# under insertion in O(log n).
from sortedcontainers import SortedList

data = [3, 6, 1, 8, 2, 9, 4]
sl = SortedList(data)
print(list(sl))               # [1, 2, 3, 4, 6, 8, 9]
sl.add(5)
print(list(sl))               # [1, 2, 3, 4, 5, 6, 8, 9]


# A toy "sorted-runs" sort that captures the spirit of cubesort:
# detect ascending runs, then merge them pairwise.
def runs_sort(arr):
    runs = []
    i = 0
    while i < len(arr):
        j = i + 1
        while j < len(arr) and arr[j] >= arr[j - 1]:
            j += 1
        runs.append(arr[i:j])
        i = j
    while len(runs) > 1:
        merged = []
        for k in range(0, len(runs), 2):
            if k + 1 < len(runs):
                merged.append(sorted(runs[k] + runs[k + 1]))
            else:
                merged.append(runs[k])
        runs = merged
    return runs[0] if runs else []


print(runs_sort([3, 6, 1, 8, 2, 9, 4]))

Trade-offs

• Designed for parallel execution; rarely beats Timsort in single-threaded Python.
• Adaptive — O(n) on already-sorted input.
• Standard library equivalent: sortedcontainers.SortedList.
• Implementation complexity is high; almost always reach for Timsort instead.

← Back to Algorithms

1. Summary

Cubesort is a comparison sort, described by Gert Boddaert, that builds a balanced multi-dimensional search structure from the input and then reads it back in order. Elements are inserted one at a time into a shallow tree of sorted index arrays whose levels act like the axes of a cube. Because each level is a sorted array, finding the insertion point needs only binary searches, and the structure stays balanced by splitting full blocks. The design is adaptive: input that already contains long ascending runs is absorbed with very few comparisons, which gives an O(n) best case, while arbitrary input costs O(n log n). It is related to B-tree-based sorting and, in its use of runs, shares ideas with natural mergesort and Timsort.

2. Adaptive runs and merging

The trace uses the run-merging view, which captures why cubesort is adaptive. The input is scanned once to find maximal ascending runs. Runs are then merged pairwise, level by level, like the bottom-up phase of mergesort. If there are r runs, there are about log r merge levels, each touching all n elements, so the cost is O(n log r). A sorted array is one run and costs a single linear pass; random data has about n/2 runs and costs O(n log n). Real cubesort gets the same effect differently: consecutive ordered inserts land in the same leaf block and append cheaply.

3. The cube-shaped index

The index can be pictured as a small number of nested sorted arrays. The top level stores boundary keys for large ranges; each child narrows the range; leaves hold short sorted runs of actual elements. Inserting an element means a binary search at each level and an insertion into a leaf, which is cheap because leaves are small. When a leaf overflows it splits and its parent receives a new boundary, keeping depth logarithmic. A final in-order traversal emits the elements sorted. Because the structure is stored as arrays rather than linked nodes, it is reasonably cache-friendly, and independent sub-ranges can be processed in parallel, which is why cubesort is often listed as a parallel sort.

4. Worked example: a simplified cubesort

The code below is a two-level teaching version: a sorted list of block maxima indexes blocks of bounded size. It shows the insert-and-split mechanics without the full multi-axis structure.

from bisect import bisect_left, insort

def simple_cubesort(data, block=4):
    blocks, maxes = [], []            # blocks[i] is sorted; maxes[i] = blocks[i][-1]
    for x in data:
        if not blocks:
            blocks.append([x]); maxes.append(x); continue
        i = bisect_left(maxes, x)     # first block whose max >= x
        if i == len(blocks):          # larger than everything: append to last block
            i -= 1
        insort(blocks[i], x)
        maxes[i] = blocks[i][-1]
        if len(blocks[i]) > block:    # split a full block
            b = blocks[i]; half = len(b) // 2
            blocks[i:i + 1] = [b[:half], b[half:]]
            maxes[i:i + 1] = [b[half - 1], b[-1]]
    return [x for b in blocks for x in b]

print(simple_cubesort([3, 6, 1, 8, 2, 9, 4]))   # [1, 2, 3, 4, 6, 8, 9]
import random
d = [random.random() for _ in range(10_000)]
assert simple_cubesort(d) == sorted(d)

Each insert does one binary search over block maxima and one insertion into a block of bounded size, so with a balanced number of blocks the total work is close to O(n log n). Adding more index levels, as real cubesort does, keeps each array small even for very large n.

5. Trade-offs and when to use

In practice cubesort is uncommon; Timsort offers the same adaptive behaviour and ships in Python and Java. The ideas behind cubesort are more useful than the algorithm itself: maintaining sorted order under streaming inserts is exactly what sortedcontainers.SortedList and B-tree indexes do.

6. Pitfalls

• Block sizes that are too small add index overhead; too large makes leaf inserts O(block).
• Splitting without updating parent boundaries corrupts the search.
• Expecting in-place behaviour: the index needs O(n) extra memory.

7. Related topics

• Timsort
• Mergesort
• Tree Sort
• Heapsort

Featured Videos