Understanding Strand Sort in Python With Example

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²)

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

Must Read

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!