Sorting means arranging items in a specified manner. Strand sort is a sorting algorithm that is recursive in nature. It is mainly used to sort a list in increasing order. In this article, we will learn how to implement strand sort in python.

Catalogue

## Strand Sort Algorithm in Python:

- Take two lists: input[], output[]
- Take another list sub[] and move the first element of input[] to it
- Now, traverse through the list input[]
- We will check every element of input[] and compare whether it is greater than the last inserted element in sub[]. If it is true, then we will add that element to sub[]; otherwise, keep it in input[]
- Now we will merge sub[] into the output[]
- The above two steps will continue until and unless all the elements of input[] are in ouput[]

## Source Code for Strand Sort:

def strand_sort(inp): output = strand(inp) while len(inp): output = merge(output, strand(inp)) return output def strand(inp): element, sub = 0, [inp.pop(0)] while element < len(inp): if inp[element] > sub[-1]: sub.append(inp.pop(element)) else: element += 1 return sub def merge(a, b): output = [] while len(a) and len(b): if a[0] < b[0]: output.append(a.pop(0)) else: output.append(b.pop(0)) output += a output += b return output inputs = [9,2,0,4,1,8,2,3,7] print("Input List:") print(inputs) output = strand_sort(inputs) print("Output List:") print(output)

## Explanation:

**strand_sort() function:**

- This function takes a list
**inp**as a parameter - In the output list, it calls the strand() function by passing inp as a parameter
- Then a while loop is implemented, which is used to
**merge the stranded list to the output list** - The while loop is continued till the input list is empty
- Finally, the
**output list is returned**as the final result

**strand() function:**

- This function also takes a list
**inp**as the parameter. - Two variables, one integer called element is initialized to 0. Another list variable sub is initialized with the first element of the input list
- A while loop is used to iterate through the inp list.
- At each iteration, the inp list element is compared with the last added element of the sub list
- if the element of the inp list is greater, it is transferred to the sub list. Otherwise, it is ignored
- Lastly, the
**sub list is returned**

**merge() function:**

- This function takes to list a and b (that needs to be merged) as parameters
- A while loop is used, which iterates till either of the lists becomes empty
- Inside the loop, the elements of both a and b are compared, and the smaller one is added to the output list
- After exiting the while loop, any remaining element in the list a or b is added to the output list
- The
**output list is then returned**

## Output:

## Time complexity:

**Best case: O(n)****Average case: O(n2)****Worst case: O(n**^{2})

## Advantages of using strand sort:

- It is more efficient than the selection sort algorithm
- The cache miss ratio for strand sort is less than that of shell sort

## Disadvantages of using strand sort:

- It is not as efficient in performance as quick sort or merge sort
- It has a complex algorithm

## Strand Sort In-depth Tutorial Video

**Video Tutorial link Click Here.**

## Must Read

- Insertion Sort in Python [Program, Algorithm, Example]
- Understanding Python Bubble Sort with examples
- Shell Sort Algorithm and Program in Python

## Conclusion:

This is how one can easily do a strand sort on a list in python. The worst-case time complexity of strand sort is O(n2), and the best case time complexity is **O(n)**. Implementation of strand sort must be done as per the needs and constraints and obviously as per a person’s personal preference.

However, if you have any doubts or questions, do let me know in the comment section below. I will try to help you as soon as possible.

*Happy Pythoning!*