Hypercube Sort: Mechanism, Complexity Analysis & Interactive Visualizer

Hypercube Sort

A parallel network routing sort: partitions elements across processors linked as a multi-dimensional hypercube, sorting data locally before routing and splitting elements along hypercube dimensions.

How it works

Hypercube Sort is designed for message-passing parallel architectures organized as a hypercube network. A hypercube of dimension \(d\) connects \(2^d\) processor nodes, where each node has a binary ID and connects directly to nodes differing by exactly 1 bit. The sorting process works as follows:

1. Local Block Sort: Divide the array of size \(n\) equally among the \(P = 2^d\) processor nodes. Each node first sorts its local elements using a fast sequential sort (like Insertion Sort or Quicksort).
2. Dimensional Routing Loop: For each dimension \(i\) from 0 to \(d-1\) of the hypercube:
   • Nodes pair up with their partners whose binary IDs differ at the \(i\)-th bit (e.g. processor 0 pairs with 1, 2 pairs with 3 in dimension 0).
   • The paired processors merge their sorted local elements.
   • Compare-Split: The processor with the lower binary ID (bit \(i = 0\)) keeps the lower half of the merged elements. The processor with the higher binary ID (bit \(i = 1\)) keeps the upper half.
3. Result: After iterating through all \(d\) dimensions, the elements are fully sorted across the hypercube nodes: node 0 contains the smallest elements, and node \(P-1\) contains the largest.

Complexity

Interactive visualization

Pseudocode

procedure hypercubeSort(A, d):
  P ← 2^d
  localBlock ← getLocalElements(A, myNodeId)
  localSort(localBlock)
  
  for dim from 0 to d - 1:
    partnerId ← myNodeId XOR (1 << dim)
    partnerBlock ← exchangeData(localBlock, partnerId)
    
    merged ← merge(localBlock, partnerBlock)
    
    if (myNodeId AND (1 << dim)) == 0:
      localBlock ← merged[0 ... length(merged)/2 - 1]
    else:
      localBlock ← merged[length(merged)/2 ... length(merged) - 1]
      
  gatherAllBlocks(A)

JavaScript implementation

// Simulating Hypercube Sort using 4 processors (2D Hypercube)
function hypercubeSort(arr) {
  const n = arr.length;
  const P = 4; // 4 nodes
  const blockSize = Math.floor(n / P);
  
  function getBounds(pid) {
    const start = pid * blockSize;
    const end = (pid === P - 1) ? n - 1 : (pid + 1) * blockSize - 1;
    return { start, end };
  }
  
  // 1. Local sort on each node
  for (let pid = 0; pid < P; pid++) {
    const { start, end } = getBounds(pid);
    // Sort block [start, end] in-place
    const block = arr.slice(start, end + 1).sort((x, y) => x - y);
    for (let i = 0; i < block.length; i++) arr[start + i] = block[i];
  }
  
  // 2. Split-merge routing over 2 dimensions
  for (let dim = 0; dim < 2; dim++) {
    const mask = 1 << dim;
    const visited = new Array(P).fill(false);
    
    for (let pid = 0; pid < P; pid++) {
      if (visited[pid]) continue;
      const partner = pid ^ mask;
      visited[pid] = visited[partner] = true;
      
      const bA = getBounds(pid);
      const bB = getBounds(partner);
      
      // Merge arrays
      const merged = [];
      let i = bA.start, j = bB.start;
      while (i <= bA.end && j <= bB.end) {
        if (arr[i] <= arr[j]) merged.push(arr[i++]);
        else merged.push(arr[j++]);
      }
      while (i <= bA.end) merged.push(arr[i++]);
      while (j <= bB.end) merged.push(arr[j++]);
      
      // Split low/high between partners
      const lowPid = Math.min(pid, partner);
      const highPid = Math.max(pid, partner);
      const bLow = getBounds(lowPid);
      const bHigh = getBounds(highPid);
      
      const half = merged.length / 2;
      for (let k = 0; k < half; k++) arr[bLow.start + k] = merged[k];
      for (let k = 0; k < half; k++) arr[bHigh.start + k] = merged[half + k];
    }
  }
  return arr;
}

Pros and cons

When (not) to use it

• Topological Supercomputers: Standard choice on parallel processing units configured with hypercube link architectures (e.g. Connection Machine).
• Standard Shared Memory: Avoid; standard Parallel Merge Sort or parallel Quicksort introduce significantly less thread mapping overhead.