Strand Sort

Strand sort builds the sorted result by repeatedly extracting increasing subsequences, called strands, from the input and merging them into an output list.

It is particularly natural for linked lists, where removing elements is efficient.

Problem

Given a sequence $A$ of length $n$ , reorder it such that

A[0] \le A[1] \le \cdots \le A[n-1]

Key Idea

Take the first element as the start of a strand
Scan the remaining elements and append those that are greater than the last strand element
Remove selected elements from the input
Merge the strand into the result
Repeat until the input is empty

Algorithm

strand_sort(A):
    result = empty list

    while A is not empty:
        strand = [A[0]]
        remove A[0] from A

        i = 0
        while i < length(A):
            if A[i] >= last(strand):
                append A[i] to strand
                remove A[i] from A
            else:
                i = i + 1

        result = merge(result, strand)

    return result

Example

Let

A = [4, 2, 5, 1, 3]

Step 1:

Extract strand:

[4, 5]

Remaining:

[2, 1, 3]

Step 2:

Extract strand:

[2, 3]

Merge with result:

[2, 3, 4, 5]

Step 3:

Extract strand:

[1]

Final result:

[1, 2, 3, 4, 5]

Correctness

Each strand is an increasing subsequence. Merging preserves sorted order. Since all elements are eventually extracted and merged, the final result is fully sorted.

Complexity

case	time
best (already sorted)	$O(n)$
worst	$O(n^2)$
average	$O(n \log n)$ with efficient merging

Space complexity:

O(n)

due to auxiliary lists.

Properties

stable
not in-place
naturally suited for linked lists
merge-based behavior

When to Use

Strand sort is useful when working with linked structures where element removal is cheap. It provides a conceptual bridge between insertion-style and merge-style sorting.

Implementation

def merge(a, b):
    result = []
    i = j = 0

    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            result.append(a[i])
            i += 1
        else:
            result.append(b[j])
            j += 1

    result.extend(a[i:])
    result.extend(b[j:])
    return result

def strand_sort(a):
    result = []

    while a:
        strand = [a.pop(0)]

        i = 0
        while i < len(a):
            if a[i] >= strand[-1]:
                strand.append(a.pop(i))
            else:
                i += 1

        result = merge(result, strand)

    return result

func merge(a, b []int) []int {
    result := []int{}
    i, j := 0, 0

    for i < len(a) && j < len(b) {
        if a[i] <= b[j] {
            result = append(result, a[i])
            i++
        } else {
            result = append(result, b[j])
            j++
        }
    }

    result = append(result, a[i:]...)
    result = append(result, b[j:]...)
    return result
}

func StrandSort(a []int) []int {
    var result []int

    for len(a) > 0 {
        strand := []int{a[0]}
        a = a[1:]

        i := 0
        for i < len(a) {
            if a[i] >= strand[len(strand)-1] {
                strand = append(strand, a[i])
                a = append(a[:i], a[i+1:]...)
            } else {
                i++
            }
        }

        result = merge(result, strand)
    }

    return result
}