Strand Sort: Mechanism, Complexity Analysis & Interactive Visualizer

Strand Sort

A unique list-extraction sorting algorithm: repeatedly pulls out sorted ascending chains (strands) from the unsorted data, merging them step-by-step into a growing sorted list.

How it works

Strand Sort is an elegant comparison-based algorithm. Instead of swapping individual elements or dividing them into binary partitions, it extracts whole sorted chains (strands) from the unsorted items and merges them together:

1. **First Strand Selection:** Take the first element of the unsorted list as the start of a new sorted list (strand).
2. **Scan and Extract:** Scan the remaining unsorted elements from left to right. For each element:
   • Compare it to the last element added to the current strand.
   • If the element is greater than or equal to the last element of the strand, pull it out of the unsorted list and append it to the strand.
3. **Merge Strand:** Merge the newly completed sorted strand into a final sorted accumulator list (using a standard merge step, similar to Mergesort).
4. **Repeat:** If there are still elements remaining in the unsorted list, repeat the process from Step 1.

Complexity

Interactive visualization

Pseudocode

procedure strandSort(A):
  sortedList ← empty list
  unsortedList ← convertToList(A)
  
  while unsortedList is not empty:
    strand ← empty list
    strand.append(unsortedList.popHead())
    
    node ← unsortedList.head
    while node is not null:
      if node.val >= strand.tail.val:
        strand.append(unsortedList.remove(node))
      node ← node.next
      
    sortedList ← merge(sortedList, strand)
    
  copyListToArray(sortedList, A)

JavaScript implementation

function strandSort(arr) {
  let unsorted = [...arr];
  let sorted = [];
  
  while (unsorted.length > 0) {
    const strand = [];
    strand.push(unsorted.shift());
    
    let i = 0;
    while (i < unsorted.length) {
      if (unsorted[i] >= strand[strand.length - 1]) {
        strand.push(unsorted.splice(i, 1)[0]);
      } else {
        i++;
      }
    }
    
    const merged = [];
    let s = 0, d = 0;
    while (s < strand.length && d < sorted.length) {
      if (strand[s] <= sorted[d]) merged.push(strand[s++]);
      else merged.push(sorted[d++]);
    }
    while (s < strand.length) merged.push(strand[s++]);
    while (d < sorted.length) merged.push(sorted[d++]);
    sorted = merged;
  }
  
  for (let i = 0; i < arr.length; i++) arr[i] = sorted[i];
  return arr;
}

Pros and cons

When (not) to use it

• Linked List Sorting: Very efficient choice if sorting linked list nodes, where popping and inserting items avoids array shifting penalties.
• Standard Arrays: Avoid; standard comparison algorithms like Timsort or Quicksort do not suffer from index-shifting overhead.