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.

Contents

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

## 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!*