Enumeration Sort: Mechanism, Complexity Analysis & Interactive Visualizer

Enumeration Sort

A parallel ranking algorithm: determines the final sorted position of each element by counting how many elements are smaller than it, sorting values directly with zero dependency between elements.

How it works

Enumeration Sort (also known as Rank Sort) is a simple parallel algorithm. Unlike other comparison sorts that iteratively swap adjacent values (like Bubble Sort) or partition subsets (like Quicksort), Enumeration Sort finds the exact destination index of each element independently:

1. Independent Rank Counting: For each element \(A[i]\) in the input list:
   • Scan the entire array and count how many elements \(A[j]\) are smaller than \(A[i]\).
   • To maintain stability (handling duplicate values), if \(A[j]\) is equal to \(A[i]\), increment the count only if \(j < i\).
2. Direct Placement: The final rank count gives the exact index slot where \(A[i]\) belongs. Write the element directly to \(dest[\text{rank}]\).
3. Perfect Parallelization: Because the rank calculations for \(A[0]\), \(A[1]\), etc. have no dependency on each other, they can all run simultaneously in parallel. On a parallel system with \(n²\) processors, the entire sort completes in \(O(1)\) time.

Complexity

Interactive visualization

Pseudocode

procedure enumerationSort(A):
  n ← length(A)
  dest ← array of size n
  
  parallel for i from 0 to n - 1:
    pos ← 0
    for j from 0 to n - 1:
      if A[j] < A[i] or (A[j] == A[i] and j < i):
        pos ← pos + 1
    dest[pos] ← A[i]
    
  copy dest back to A

JavaScript implementation

function enumerationSort(arr) {
  const n = arr.length;
  const dest = new Array(n);
  
  for (let i = 0; i < n; i++) {
    let pos = 0;
    for (let j = 0; j < n; j++) {
      if (arr[j] < arr[i] || (arr[j] === arr[i] && j < i)) {
        pos++;
      }
    }
    dest[pos] = arr[i];
  }
  
  for (let i = 0; i < n; i++) {
    arr[i] = dest[i];
  }
  return arr;
}

Pros and cons

When (not) to use it

• Massive Parallel Networks: Ideal for specialized SIMD architectures or FPGA networks where all ranks can be counted simultaneously.
• Standard Programming: Never use sequentially; comparison sorts like Mergesort or Quicksort are orders of magnitude faster.