Cube Sort: Mechanism, Complexity Analysis & Interactive Visualizer

Cube Sort

A parallel dimension sorting algorithm: organizes elements in a 3D coordinate cube and sorts vectors along the height, width, and depth axes sequentially to achieve sorted order.

How it works

Cube Sort organizes elements into a multi-dimensional coordinate space (historically a 3D grid or a hypercube structure) to perform parallel dimension-wise sorting sweeps. Organizing the array of size \(n = d^3\) as a 3D cube of dimensions \(d \times d \times d\) (e.g. \(3 \times 3 \times 3 = 27\) elements) allows sorting elements along independent coordinate axes:

1. **Z-Axis Sweep (Height):** Sort all 1D vertical columns of the cube. That is, for every fixed \((x, y)\) pair, sort the vector \([A(x, y, 0), A(x, y, 1), A(x, y, 2)]\).
2. **Y-Axis Sweep (Width):** Sort all 1D horizontal rows of the cube. For every fixed \((x, z)\) pair, sort the vector \([A(x, 0, z), A(x, 1, z), A(x, 2, z)]\).
3. **X-Axis Sweep (Depth):** Sort all 1D depth lanes of the cube. For every fixed \((y, z)\) pair, sort the vector \([A(0, y, z), A(1, y, z), A(2, y, z)]\).
4. **Cleanup Sweep:** Because axis sorting brings the overall cube highly close to sorted order but doesn't guarantee a strict linear sort (as diagonal items can remain out of order), a final quick linear sorting sweep (like Insertion Sort) is executed to fully sort the array.

Complexity

Interactive visualization

Pseudocode

procedure cubeSort(A):
  # organizing A as a 3D grid of size d x d x d
  d ← cubeRoot(length(A))
  
  # Step 1: Sort Z-Axis columns
  for x from 0 to d - 1:
    for y from 0 to d - 1:
      sortVector(A[x][y][0 ... d-1])
      
  # Step 2: Sort Y-Axis rows
  for x from 0 to d - 1:
    for z from 0 to d - 1:
      sortVector(A[x][0 ... d-1][z])
      
  # Step 3: Sort X-Axis lanes
  for y from 0 to d - 1:
    for z from 0 to d - 1:
      sortVector(A[0 ... d-1][y][z])
      
  # Step 4: Final cleanup sweep
  insertionSortSweep(A)

JavaScript implementation

function cubeSort(arr) {
  const n = arr.length;
  const S = 3; // 3x3x3 cube = 27
  
  function getIdx(x, y, z) {
    return x * S * S + y * S + z;
  }
  
  // 1. Z-Axis
  for (let x = 0; x < S; x++) {
    for (let y = 0; y < S; y++) {
      const idxs = [getIdx(x, y, 0), getIdx(x, y, 1), getIdx(x, y, 2)];
      sortVector(arr, idxs);
    }
  }
  
  // 2. Y-Axis
  for (let x = 0; x < S; x++) {
    for (let z = 0; z < S; z++) {
      const idxs = [getIdx(x, 0, z), getIdx(x, 1, z), getIdx(x, 2, z)];
      sortVector(arr, idxs);
    }
  }
  
  // 3. X-Axis
  for (let y = 0; y < S; y++) {
    for (let z = 0; z < S; z++) {
      const idxs = [getIdx(0, y, z), getIdx(1, y, z), getIdx(2, y, z)];
      sortVector(arr, idxs);
    }
  }
  
  // 4. Final Cleanup Sweep
  for (let i = 1; i < n; i++) {
    let key = arr[i], j = i - 1;
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = key;
  }
  return arr;
}

function sortVector(arr, idxs) {
  const vals = idxs.map(i => arr[i]).sort((x, y) => x - y);
  for (let i = 0; i < idxs.length; i++) arr[idxs[i]] = vals[i];
}

Pros and cons

When (not) to use it

• SIMD processor grids: Standard choice on parallel processing grids organized as a 3D matrix where memory channels are divided by axes.
• Standard CPUs: Avoid; in-memory comparison sorts like Quicksort or Timsort are much faster and simpler.