Strand sort

Key takeaways

Strand sort belongs to computer science; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect Strand sort to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Strand sort from memory before moving on to harder problems.

Reference excerpt

Strand sort is a recursive sorting algorithm that sorts items of a list into increasing order. It has O(n2) worst-case time complexity, which occurs when the input list is reverse sorted. It has a best-case time complexity of O(n), 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.

Example This example is based on the description of the algorithm provided in the book IT Enabled Practices and Emerging Management Paradigms. Step 1: Start with a list of numbers: {5, 1, 4, 2, 0, 9, 6, 3, 8, 7}. Step 2: Next, move the first element of the list into a new sub-list: sub-list contains {5}. Step 3: Then, iterate through the original list and compare each number to 5 until there is a number greater than 5.

1 < 5, so 1 is not added to the sub-list. 4 < 5, so 4 is not added to the sub-list. 2 < 5, so 2 is not added to the sub-list. 0 < 5, so 0 is not added to the sub-list. 9 > 5, so 9 is added to the sub-list and removed from the original list. Step 4: Now compare 9 with the remaining elements in the original list until there is a number greater than 9.

6 < 9, so 6 is not added to the sub-list. 3 < 9, so 3 is not added to the sub-list. 8 < 9, so 8 is not added to the sub-list. 7 < 9, so 7 is not added to the sub-list. Step 5: Now there are no more elements to compare 9 to, so merge the sub-list into a new list, called solution-list. After step 5, the original list contains {1, 4, 2, 0, 6, 3, 8, 7}. The sub-list is empty, and the solution list contains {5, 9}. Step 6: Move the first element of the original list into sub-list: sub-list contains {1}. Step 7: 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 and 4 is removed from the original list. Step 8: Now compare 4 with the remaining elements in the original list until there is a number greater than 4.

2 < 4, so 2 is not added to the sub-list. 0 < 4, so 0 is not added to the sub-list. 6 > 4, so 6 is added to the sub-list and is removed from the original list. Step 9: Now compare 6 with the remaining elements in the original list until there is a number greater than 6.

3 < 6, so 3 is not added to the sub-list. 8 > 6, so 8 is added to the sub-list and is removed from the original list. Step 10: Now compare 8 with the remaining elements in the original list until there is a number greater than 8.

7 < 8, so 7 is not added to the sub-list. Step 11: Since there are no more elements in the original list to compare {8} to, the sub-list is merged with the solution list. Now the original list contains {2, 0, 3, 7}, the sub-list is empty, and the solution-list contains {1, 4, 5, 6, 8, 9}. Step 12: Move the first element of the original list into sub-list. Sub-list contains {2}. Step 13: Iterate through the original list and compare each number to 2 until there is a number greater than 2.

0 < 2, so 0 is not added to the sub-list. 3 > 2, so 3 is added to the sub-list and is removed from the original list. Step 14: Now compare 3 with the remaining elements in the original list until there is a number greater than 3.

7 > 3, so 7 is added to the sub-list and is removed from the original list. Step 15: Since there are no more elements in the original list to compare {7} to, the sub-list is merged with the solution list. The original list now contains {0}, the sub-list is empty, and solution list contains {1, 2, 3, 4, 5, 6, 7, 8, 9}. Step 16: Move the first element of the original list into sub-list. Sub-list contains {0}. Step 17: Since the original list is now empty, the sub-list is merged with the solution list. The solution list now contains {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. There are now no 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 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.

References

Illustrations

Worked examples

Example 1 — a first encounter with Strand sort

Start with the simplest possible case. Write down what Strand sort claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In computer science, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Strand sort before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Strand sort ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Strand sort

In research: Strand sort appears in computer science research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses Strand sort in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: Strand sort is common in secondary-school and first-year university syllabi. It links to neighbouring topics Sorting algorithms, so understanding it makes those chapters shorter.
In everyday life: Look for Strand sort outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

How to study Strand sort in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Strand sort means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain Strand sort out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Strand sort in simple terms?

Strand sort is a recursive sorting algorithm that sorts items of a list into increasing order. It has O(n2) worst-case time complexity, which occurs when the input list is reverse sorted.

Why does Strand sort matter?

Because it connects several computer science ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Strand sort?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Strand sort.