# Strand Sort in C++

In this tutorial, we will learn about one of the commonly used **sorting** algorithms i.e. **Strand sort in C++ with algorithm**. Before this I recommend you to read the tutorial on **merge sort**. This will help you to understand this algorithm easily.

Strand sort is generally used to sort elements in ascending order.

**‘Sorting’ **in programming refers to the arrangement of a sequence in either ascending or descending order.

**‘Array’ **is a data structure used in programming to store multiple variables of the same type.

**‘Vectors’ **are the dynamic arrays with the capability to resize themselves.

**Algorithm for Strand Sort**

#### strand_sort( int n, int a[] )

- This function takes input array and it’s size as parameters.
- Firstly we create an empty vector, which will store the sorted sequences from the input array.
- And we will mark these elements as taken using
**flag**array. - We will also define an empty output vector.
- Then step by step we will take a sorted sequence and merge it with the output vector until all the input elements are taken.
- Then we will finally report the output vector.

#### merge(vector<int>&c)

- We will use this function to merge the sorted sequences with the output vector.
- We take a sorted sequence as the parameter.
- We will define a temporary vector which will be the same as the output vector computed in the previous step.
- Then we will set two pointers onto the first elements of the two vectors respectively.
- Now we will compare the two pointers and insert the smaller one into the output vector until one of the pointers reaches the end of the vector.
- Lastly, we will insert the remaining elements of the vector into the output vector.

**Time Complexity of the Algorithm of Strand Sort in C++**

The time complexity of this algorithm will be** O(n) **in the best case and **O(n²) **in the worst case**.**

- The best-case will be when the input array is already in ascending order.
- The worst-case will be when the input array is in descending order.

**C++ Code for the Algorithm**

#include<bits/stdc++.h> using namespace std; vector<int>b; // output vector //merge vector c into output vector void merge( vector<int>&c ){ vector<int>d; d=b; b.clear(); int i = 0, j = 0; while (i<c.size() && j <d.size()) { if (c[i]<d[j]){ b.push_back(c[i]); i++; } else{ b.push_back(d[j]); j++; } } while (i<c.size()){ b.push_back(c[i]); i++; } while (j<d.size()){ b.push_back(d[j]); j++; } } //strand sort function void strand_sort( int n, int a[] ){ int flag[n]; //used to mark that this element is in the output vector(1) or not(0) memset(flag,0,sizeof(flag)); //sets initially none of the element is in output vector int k=n; //used to store how many elements are left in input array vector<int>c; //temporary vector used to store sorted sequences from input array //this while loop step by step inserts all sorted sequences from //input array to output vector while(k>0){ int h=0; for(int x=0; x<n; x++){ if(flag[x]==0&&a[x]>=h){ k--; flag[x]=1; c.push_back(a[x]); h=a[x]; } } merge(c); //used to merge the small sorted sequences into output vector c.clear(); } } //driver function int main() { int n; //size of the input array cin>>n; int a[n]; //input array for(int x=0; x<n; x++){ cin>>a[x]; } strand_sort(n,a); //Here we calls the strand sort function for(int x=0; x<n; x++){ cout<<b[x]<<" "; //output of the final sorted array } cout<<"\n"; return 0; }

**Input**

5 5 2 4 3 1

**Output**

1 2 3 4 5

Some other sorting Algorithms

## Leave a Reply