Size:15

Overview & Concept

Strand Sort is a recursive or iterative sorting algorithm that repeatedly pulls ordered sub-sequences ("strands") from an unsorted pool of elements and merges them into an accumulating sorted output list. It achieves linear O(n) performance on already sorted lists.

How It Works

Unsorted Pool: Maintained as a list containing elements that have not yet been incorporated into strands.

Greedy Strand Extraction: Pulls the first element into a new strand, then scans the pool, extracting any elements greater than or equal to the last strand item.

Two-Way Merge: Merges the newly extracted strand into the accumulating sorted master list.

Iterative Repeat: Continues extracting and merging until the unsorted pool is completely exhausted.

Step-by-Step Execution

1. Initialize Output ListSet output = [] and pool = copy(input).

2. Extract Active StrandPull first pool item into strand; greedily append non-decreasing items from pool.

3. Merge into OutputExecute two-way sorted merge of active strand with current output list.

4. Repeat until Pool EmptyContinue until all elements reside in the output list.

Asymptotic Complexity Analysis

Metric	Best Case	Average Case	Worst Case	Space Complexity
Complexity Bound	O(n)	O(n²)	O(n²)	O(n)
Explanation	Optimal input arrangement minimizing operations.	Expected time for uniformly distributed randomized inputs.	Adversarial degenerate conditions requiring full traversal.	Auxiliary memory allocated beyond original input size.

Pseudocode & Invariants

Algorithm Logic

procedure strandSort(A):
  output = []
  while length(A) > 0:
    strand = [popFront(A)]
    for each item in A:
      if item >= last(strand): strand.append(item); remove item from A
    output = merge(output, strand)
  return output

Algorithmic Invariants

Strand Monotonicity: Each extracted strand is strictly non-decreasing.
Output Sortedness: The accumulated output list remains sorted after every merge step.

Correctness Guarantee: Invariants hold true prior to loop entry, are preserved during every iteration, and guarantee correct post-condition upon termination.

Advantages & Disadvantages

Key Advantages

•O(n) best-case time complexity when input is already sorted.
•Stable sorting behavior preserves duplicate item ordering.
•Highly efficient when implemented on linked lists due to O(1) removal without element shifting.

Trade-offs & Limitations

•O(n²) worst-case time complexity on reverse-sorted inputs (each strand has length 1).
•Requires auxiliary list storage for the remainder pool, active strand, and output.

Real-World Applications

Linked List Sorters

Ideal for singly-linked lists where nodes can be spliced and merged with pointer rewiring.

Decision Guide: When to Use

Ideal Scenarios

✓When sorting data structures organized as linked lists rather than contiguous arrays.
✓When input contains long runs of pre-sorted elements.

Consider Alternatives When

✕On reverse-sorted arrays or when contiguous array shifting overhead is high.

Compare trade-offs and complexity across complementary tools in AlgoViz.

Merge Sort Insertion Sort TimSort