Strand Sort

Strand Sort is a sorting algorithm that works in O(n) time if list is already sorted and works in O(n*n) in worst case.

Given a list of items, sort them in increasing order:

Input : ip[] = {10, 5, 30, 40, 2, 4, 9}
Output : op[] = {2, 4, 5, 9, 10, 30, 40}

Input : ip[] = {1, 10, 7}
Output : op[] = {1, 7, 10}

Below are simple steps used in the algorithm.

1. Let ip[] be input list and op[] be output list.
2. Create an empty sublist and move first item of ip[] to it.
3. Traverse remaining items of ip. For every item x, check if x is greater than last inserted item to sublist. If yes, remove x from ip and add at the end of sublist. If no, ignore x (Keep it it in ip)
4. Merge sublist into op (output list)
5. Recur for remaining items in ip and current items in op.

Illustration :

Let ip[] = {10, 5, 30, 40, 2, 4, 9}
Initialize : op[] = {}
             sublist[] = {}

Move first item of ip to sublist.
sublist[] = {10}

Traverse remaining items of ip and
if current element is greater than
last item of sublist, move this item
from ip to sublist. Now
sublist[] = {10, 30, 40}
ip[] = {5, 2, 4, 9}
                
Merge sublist into op.
op = {10, 30, 40}

Next recursive call:
Move first item of ip to sublist.
sublist[] = {5}

Traverse remaining items of ip and move
elements greater than last inserted.
ip[] = {2, 4}
sublist[] = {5, 9}

Merge sublist into op.
op = {5, 9, 10, 30, 40}

Last Recursive Call:
{2, 4} are first moved to sublist and
then merged into op.
op = {2, 4, 5, 9, 10, 30, 40}

CODE:

# Python program for Strand Sort. Note that this program 
def merge_list(a, b):
  out = []
  while len(a) and len(b):
    if a[0] < b[0]:
      out.append(a.pop(0))
    else:
      out.append(b.pop(0))
  out += a
  out += b
  return out
 
def strand(a):
  i, s = 0, [a.pop(0)]
  while i < len(a):
    if a[i] > s[-1]:
      s.append(a.pop(i))
    else:
      i += 1
  return s
 
def strand_sort(a):
  out = strand(a)
  while len(a):
    out = merge_list(out, strand(a))
  return out
 
 
numbers = [2,4,6,8,10,9,7,5,3,1]
print(numbers)
 
numbers = strand_sort(numbers)
print(numbers)

Output:           
[2, 4, 6, 8, 10, 9, 7, 5, 3, 1]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Complexity

Worst complexity: n^2
Average complexity: n^2
Best complexity: n
Space complexity: n
Method: Selection
Stable: Yes
Class: Comparison sort