Strand sort

Strand Sort Animation

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

Performance

Strand sort has a worst case time complexity of O(n²) which occurs when the input list is reverse sorted. 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. Its average case complexity is O(n log n). Compared to other sorting algorithms, strand sort is on the slower side.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).

Example

Based off of the description of the algorithm provided in the book, IT 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.

Implementation

Since Strand Sort requires many insertions and deletions, it is best to use a linked list when implementing strand sort. Linked lists require constant time for both insertions and removals of elements using iterators. Linked lists can only access sequential elements, which is what strand sort does. 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 off of 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<Integer> solList = new LinkedList<Integer>();
	static int k = 0;

	/**
	 * This is a recursive Strand Sort method. It takes in a linked list of
	 * integers as parameters. It first check 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<Integer> 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<Integer> subList = new LinkedList<Integer>();
			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 < origList.size(); j++) {
				if (origList.get(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 three 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 < subList.size(); i++) {

					solList.add(subList.get(i));
					k = k + 1;
				}

			}
			// Case 2: After the first recursive call if there subList contains
			// more than one element,
			// the elements need to be added to
			// The front of the solution list, adding the largest element first.
			else if (subList.size() > 1) {
				for (int w = subList.size() - 1; w >= 0; w--) {
					solList.addFirst(subList.get(w));

					// w = w+1;

				}
			} else {
				// If there is only one element in the subList, then
				// It just gets added to the front of the solution list.
				for (int w = 0; w < subList.size(); w++) {

					solList.addFirst(subList.get(w));

				}

			}
			strandSortIterative(origList);

		}

	}

	public static void main(String[] args) {
		// Create a new linked list of Integers
		LinkedList<Integer> origList = new LinkedList<Integer>();

		// Add the following integers to the linked list: {13, 7, 19, 6, 25, 29,
		// 1, 4}

		origList.add(13);
		origList.add(7);
		origList.add(19);
		origList.add(6);
		origList.add(25);
		origList.add(29);
		origList.add(1);
		origList.add(4);

		strandSortIterative(origList);
		// Print out the solution list
		for (int i = 0; i < solList.size(); i++) {
			System.out.println(solList.get(i));
		}

	}

}