What is strand sort?

Divide the list: Start by dividing the unsorted list into several strands. Starting from the first element, as soon as the list value is less than the previous value, it is assigned a new strand. This ensures each strand represents small, sorted sublists.
Merge the strands: Repeatedly merge them by taking elements from one strand and inserting them into another while maintaining the sorted order. This merging process continues until no more elements can be merged.
Repeat: The steps above are repeated until all elements have been merged into a single sorted list.

How does it work?

To understand how strand sort works, we will consider a simple example with an unsorted list as follows: $[3, 1, 4, 2, 5]$

In the first iteration, a strand starting from $3$ is created. Subsequent values that are greater are appended to the list and removed from the unsorted list. Hence, the first strand consists of $[3,4,5]$ .
In the next iteration, a strand starting from $1$ is created. Following the same rule, the second strand consists of $[1,2]$ .
Finally, these are merged into one sorted list: $[1,2,3,4,5]$ .

def strand_sort(input_list):
    # Strand merging function
    def merge_strands(strand1, strand2):
        result = []
        while strand1 and strand2:
            if strand1[0] < strand2[0]:
                result.append(strand1.pop(0))
            else:
                result.append(strand2.pop(0))
        result += strand1
        result += strand2
        return result
    # An Edge case for when list is empty or one element
    if len(input_list) <= 1:
        return input_list
    # Initialize a strand with the first element
    strand = [input_list.pop(0)]
    i = 0
    while i < len(input_list):
        if input_list[i] > strand[-1]:
            strand.append(input_list.pop(i))
        else:
            i += 1
    sorted_strand = strand
    remaining_list = strand_sort(input_list)
    # Merge the sorted strands
    return merge_strands(sorted_strand, remaining_list)
# Use the function
unsorted_list = [3, 1, 4, 1, 5, 9, 2, 6]
print("Unsorted List:", unsorted_list)
sorted_list = strand_sort(unsorted_list)
print()
print("Sorted List:", sorted_list)

The strand_sort(input_list) is the main function that takes an unsorted list input_list as input and returns the sorted list using the strand sort algorithm. Here is how the function works:

Lines 3–13: merge_strands(strand1, strand2) is a helper function that takes two sorted strands, strand1 and strand2, and merges them into a single sorted strand. It uses a while loop to compare the first elements of the two strands and appends the smaller of the two to the result list. This process continues until one of the strands becomes empty. Then, the remaining elements from both strands are added to the result. The final result is a merged list containing all elements from the input strands in sorted order.
Lines 15–17: We check if the length of the input_list is less than or equal to 1. If true, return the input list as it is.
Lines 23–28: A while loop iterates through the input_list. If the current element (input_list[i]) is greater than the last element of the strand (strand[-1]), we append the current element to the strand and remove it from the input_list. If not, we increment the index i.
Lines 30–34:. We set sorted_strand to the current state of the strand and recursively call the strand_sort function on the remaining elements in the remaining_list. When the recursion ends, we use the merge_strands function to merge the strands and return the merged output.

Complexity

Time complexity: In the worst-case scenario, where the input list is in reverse order, the strand sort algorithm exhibits a time complexity of $O(n^2)$ , where $n$ is the number of elements in the list. This is because, in each iteration of merging strands, it can potentially compare and merge all elements in the list.
Space complexity: In the worst-case scenario, the space complexity of the strand sort algorithm is $O(n)$ , where $n$ is the number of elements in the list. This is because it creates a series of strands, each containing some elements from the input list. When there is no merging happening, it may create $n$ strands, each containing one element, effectively copying the entire input list. However, as the merging proceeds, the number of strands decreases, and the space complexity becomes more efficient.

Conclusion

Strand sort is a unique sorting algorithm that uses strands to sort data gradually. While it may not be the most efficient choice for large datasets, it offers a simple and educational approach to sorting algorithms. Understanding different sorting techniques, including strand sort, can be valuable for solving various computational problems and expanding your knowledge of algorithms.

Free Resources

Learn in-demand tech skills in half the time

PRODUCTS

Mock Interview

New

Courses

Skill Paths

Projects

Assessments

Pros	Cons
It is simple to understand and implement.	It’s inefficient for large datasets compared to more advanced sorting algorithms like quick or merge sort.
It is adaptive to partially sorted lists.	It may not be the best choice for practical applications where speed is essential.

What is strand sort?

Strand sort

How does it work?

Algorithm

Pros and cons

Complexity

Conclusion