# Strand Sort

# 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

```id="k1x9p3"
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

```id="m3x8q2"
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
```

```id="z6k2v3"
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
}
```