strand sort


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

Entry modified 24 November 2008.
HTML page formatted Tue Dec 6 16:16:33 2011.

Cite this as:
Paul E. Black, "strand sort", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 24 November 2008. (accessed TODAY) Available from:

to NIST home page