NIST

strand sort

(algorithm)

Definition: A sort algorithm that works well if many items are in order. First, begin a sublist by moving the first item from the original list to the sublist. For each subsequent item in the original list, if it is greater than the last item of the sublist, remove it from the original list and append it to the sublist. Merge the sublist into a final, sorted list. Repeatedly extract and merge sublists until all items are sorted. Handle two or fewer items as special cases.

Generalization (I am a kind of ...)
distribution sort.

Aggregate parent (I am a part of or used in ...)
J sort.

See also selection sort, merge sort, UnShuffle sort.

Note: This works especially well with linked lists.

Author: PEB

More information

Explained in a message about J sort posted in 1997.


Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 24 November 2008.
HTML page formatted Mon Feb 2 13:10:40 2015.

Cite this as:
Paul E. Black, "strand sort", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 24 November 2008. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/strandSort.html