#strand-sort

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...