Strand sort

Strand sort is a recursive sorting algorithm that sorts items of a list into increasing order. It has worst-case time complexity, which occurs when the input list is reverse sorted. It has a best-case time complexity of , which occurs when the input is already sorted. The algorithm first moves the first element of a list into a sub-list. It then compares the last element in the sub-list to each subsequent element in the original list. Once there is an element in the original list that is greater than the last element in the sub-list, the element is removed from the original list and added to the sub-list. This process continues until the last element in the sub-list is compared to the remaining elements in the original list. The sub-list is then merged into a new list. Repeat this process and merge all sub-lists until all elements are sorted. This algorithm is called strand sort because there are strands of sorted elements within the unsorted elements that are removed one at a time. This algorithm is also used in J Sort for fewer than 40 elements.

Strand sort is a recursive sorting algorithm that sorts items of a list into increasing order. It has worst-case time complexity, which occurs when the input list is reverse sorted. It has a best-case time complexity of , which occurs when the input is already sorted. The algorithm first moves the first element of a list into a sub-list. It then compares the last element in the sub-list to each subsequent element in the original list. Once there is an element in the original list that is greater than the last element in the sub-list, the element is removed from the original list and added to the sub-list. This process continues until the last element in the sub-list is compared to the remaining elements in the original list. The sub-list is then merged into a new list. Repeat this process and merge all sub-lists until all elements are sorted. This algorithm is called strand sort because there are strands of sorted elements within the unsorted elements that are removed one at a time. This algorithm is also used in J Sort for fewer than 40 elements. Since Strand Sort requires many insertions and deletions, it is best to use a linked list when implementing the algorithm. Linked lists require constant time for both insertions and removals of elements using iterators. The time to traverse through the linked list is directly related to the input size of the list. The following implementation is done in Java 8 and is based on the description of the algorithm from the book IT Enabled Practices and Emerging Management Paradigms. package strandSort; import java.util.*; public class strandSort { static LinkedList solList = new LinkedList (); static int k = 0; /** * This is a recursive Strand Sort method. It takes in a linked list of * integers as its parameter. It first checks the base case to see if the * linked list is empty. Then proceeds to the Strand sort algorithm until * the linked list is empty. * * @param origList: * a linked list of integers */ public static void strandSortIterative(LinkedList origList) { // Base Case if (origList.isEmpty()) { return; } else { // Create the subList and add the first element of // The original linked list to the sublist. // Then remove the first element from the original list. LinkedList subList = new LinkedList (); subList.add(origList.getFirst()); origList.removeFirst(); // Iterate through the original list, checking if any elements are // Greater than the element in the sub list. int index = 0; for (int j = 0; j subList.get(index)) { subList.add(origList.get(j)); origList.remove(j); j = j - 1; index = index + 1; } } // Merge sub-list into solution list. // There are two cases for this step/ // Case 1: The first recursive call, add all of the elements to the // solution list in sequential order if (k == 0) { for (int i = 0; i solList.get(solStart)) { solStart++; } else { solList.add(solStart, subList.get(subEnd)); subList.remove(subEnd); subEnd--; solStart = 0; } } } strandSortIterative(origList); } } public static void main(String[] args) { // Create a new linked list of Integers LinkedList origList = new LinkedList (); // Add the following integers to the linked list: {5, 1, 4, 2, 0, 9, 6, 3, 8, 7} origList.add(5); origList.add(1); origList.add(4); origList.add(2); origList.add(0); origList.add(9); origList.add(6); origList.add(3); origList.add(8); origList.add(7); strandSortIterative(origList); // Print out the solution list for (int i = 0; i

Text derived from https://en.wikipedia.org/w/index.php?oldid=1260344656 under CC BY-SA 4.0; modifications have been made.