Strand sort

Strand sort is a very simple recursive sorting algorithm that sorts items of a list into increasing order. It works by moving the first element of a list into a sub-list. Then comparing each subsequent element in the sub-list to the original list and moving each element in the original list that is greater than the element in the sub-list to the sub-list. Then the sub-list is merged into a new list. Repeat this process and merge all sub-lists until all elements are sorted.^[1] This algorithm is called strand sort because there are strands of sorted elements within the unsorted elements that are removed one at a time.^[2] This algorithm is also comparison sorting algorithm because elements of the sub-list are compared to elements of the original list. This algorithm is also used in J Sort for fewer than 40 elements.^[3]

Performance

Strand sort has a worst case time complexity of O(n²) which occurs when the input list is reverse sorted.^[1] Where n represents the total number of elements being sorted. Strand sort has a best case time complexity of O(n) which occurs when the input is a list that is already sorted.^[2] Its average case complexity is O(n log n).^[1] Compared to other sorting algorithms, strand sort is on the slower side.^[1]Strand sort is stable due to the fact that the relative order of the elements of the same value does not change. Strand sort is not in-place because it’s space complexity is O(n).^[1]

Example

Based off of the description of the algorithm provided in the bookIT enabled practices and emerging management paradigms.

Step 1: Start with a list of numbers: {13, 7, 19, 6, 25, 29, 1, 4 }

Step 2: Next move the first element of the list into a new sub-list: sub-list contains {13}

Step 3: Then iterate through the original list and compare each number to 13 until there is a number greater than 13.

2 < 13 so 7 is not added to the sub-list. 19 > 13 so 19 is added to the list.

Step 4: Now compare 19 with the remaining elements in the original list until there is a number greater than 19.

6 < 19 so 6 is not added to the list. 25 > 19 so 25 is added to the sub-list.

Step 5: Now compare 25 to the remaining elements in the original list until there is a number greater than 25.

29 > 25 so 29 is added to the sub-list.

Step 6: Now compare 29 to the remaining elements in the original list until there is a number greater than 29.

29 > 1 so 1 is not added to the sub-list. 29 > 4 so 4 is not added to the sub-list.

Step 7: Merge the sub-list into a new list, called solution-list.

After step 7, the original list contains {7, 6, 1, 4}

The sub-list is empty, and the solution list contains {13, 19, 25, 19}

Step 8: Move the first element of the original list into sub-list: sub-list contains {7}

Step 9: Iterate through the original list and compare each number to 7 until there is a number greater than 7.

6 < 7 so 6 is not added to the sub-list. 1 < 7 so 1 is not added to the sub-list. 4 < 7 so 4 is not added to the sub list.

Step 10: Merge sub-list with solution-list. Now sub-list is empty and solution-list contains: {7, 13, 19, 25, 19}.

Step 11: Move the first element of the original list into sub-list. Sub-list contains {6}

Step 12: Iterate through the original list and compare each number to 6 until there is a number greater than 6.

1 < 6 so 1 is not added to the sub-list. 4 < 6 so 4 is not added to the sub-list.

Step 13: Since there are no more elements in the original list to compare {6} to, the sub-list is merged with the solution list.

The solution list now contains: {6, 7, 13, 19, 25, 19}.

Step 14: Move the first element of the original list into sub-list. Sub-list contains {1}

Step 15: Iterate through the original list and compare each number to 1 until there is a number greater than 1.

4 > 1 so 4 is added to the sub-list.

Step 16: Since there are no more elements in the original list to compare {4} to, the sub-list is merged with the solution list.

The solution list now contains: {1,4, 6, 7, 13, 19, 25, 19}. There are now more elements in the original list, and all of the elements in the solution list have successfully been sorted into increasing numerical order.

References

^ ^a ^b ^c ^d ^e IT enabled practices and emerging management paradigms. Gupta, I. C. (Ishwar Chandra), 1946-, Jaroliya, Deepak., Prestige Institute of Management and Research. (1st ed ed.). Indore: Prestige Institute of Management and Research. 2008. ISBN 9788174466761. OCLC 641462443. {{cite book}}: |edition= has extra text (help)CS1 maint: others (link)
^ ^a ^b "strand sort". xlinux.nist.gov. Retrieved 2018-11-06.
^ Sudipta., Mukherjee, (2008). Data structures using C : 1000 problems and solutions. New Delhi: Tata McGraw-Hill. ISBN 9780070667655. OCLC 311311576.{{cite book}}: CS1 maint: extra punctuation (link) CS1 maint: multiple names: authors list (link)

[:0-1] IT enabled practices and emerging management paradigms. Gupta, I. C. (Ishwar Chandra), 1946-, Jaroliya, Deepak., Prestige Institute of Management and Research. (1st ed ed.). Indore: Prestige Institute of Management and Research. 2008. ISBN 9788174466761. OCLC 641462443. {{cite book}}: |edition= has extra text (help)CS1 maint: others (link)

[:1-2] "strand sort". xlinux.nist.gov. Retrieved 2018-11-06.

[3] Sudipta., Mukherjee, (2008). Data structures using C : 1000 problems and solutions. New Delhi: Tata McGraw-Hill. ISBN 9780070667655. OCLC 311311576.{{cite book}}: CS1 maint: extra punctuation (link) CS1 maint: multiple names: authors list (link)

[1]

[2]

[3]