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