# Strand Sort

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

Examples:

```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}
```

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.

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}```

Below is the implementation of above algorithm. The C++ implementation uses list in C++ STL.

 `// CPP program to implement Strand Sort ` `#include ` `using` `namespace` `std; ` ` `  `// A recursive function to implement Strand ` `// sort. ` `// ip is input list of items (unsorted). ` `// op is output list of items (sorted) ` `void` `strandSort(list<``int``> &ip, list<``int``> &op) ` `{ ` `    ``// Base case : input is empty ` `    ``if` `(ip.empty()) ` `        ``return``; ` ` `  `    ``// Create a sorted sublist with ` `    ``// first item of input list as ` `    ``// first item of the sublist ` `    ``list<``int``> sublist; ` `    ``sublist.push_back(ip.front()); ` `    ``ip.pop_front(); ` `      `  `    ``// Traverse remaining items of ip list ` `    ``for` `(``auto` `it = ip.begin(); it != ip.end(); ) { ` ` `  `        ``// If current item of input list ` `        ``// is greater than last added item ` `        ``// to sublist, move current item ` `        ``// to sublist as sorted order is ` `        ``// maintained. ` `        ``if` `(*it > sublist.back()) { ` `            ``sublist.push_back(*it); ` ` `  `            ``// erase() on list removes an ` `            ``// item and returns iterator to ` `            ``// next of removed item. ` `            ``it = ip.erase(it); ` `        ``} ` ` `  `        ``// Otherwise ignore current element ` `        ``else` `            ``it++; ` `    ``} ` ` `  `    ``// Merge current sublist into output ` `    ``op.merge(sublist); ` ` `  `    ``// Recur for remaining items in ` `    ``// input and current items in op. ` `    ``strandSort(ip, op); ` `} ` ` `  `// Driver code ` `int` `main(``void``) ` `{ ` `    ``list<``int``> ip{10, 5, 30, 40, 2, 4, 9}; ` ` `  `    ``// To store sorted output list ` `    ``list<``int``> op; ` ` `  `    ``// Sorting the list ` `    ``strandSort(ip, op); ` ` `  `    ``// Printing the sorted list ` `    ``for` `(``auto` `x : op) ` `        ``cout << x << ``" "``; ` `    ``return` `0; ` `} `

/div>
Output:

```2 4 5 9 10 30 40
```

More Sorting Algorithms :

## tags:

Sorting cpp-list STL Sorting STL