INSERTION SORT IN C++ ( PART1 OF SORTING ALGORITHMS)

//

//  main.cpp

//  Exp

//

//  Created by Manish on 07/11/19.

//  Copyright © 2019 Manish. All rights reserved.

//

#include <iostream>

#include <vector>

using namespace std;

vector<int> insertionSort(vector<int> &myVector)

{

   //left index

    int leftIndex;

    //key element

    int key;

    //loop from first index to length-1

    for(int i=1;i!=myVector.size();i++)

    {

        //store first element in inside key

        key=myVector[i];

        leftIndex=i-1;

        //swap element until left is greator than right and leftindex >=0

        while (leftIndex>=0 && myVector[leftIndex]>key) {

            

            myVector[leftIndex+1]=myVector[leftIndex];

            leftIndex=leftIndex-1;

        }

        myVector[leftIndex+1]=key;

    }

    

    return myVector;

};

int main(int argc, const char * argv[]) {

    //insertion sort would be good on very small array

    vector<int> myVector={11,21,7,3,89,15};

    //pass vector

    insertionSort(myVector);

    //print vector

    for(auto x:myVector)

    {

        cout<<x<<endl;

    }

    return 0;

}

COPY AND PASTE CODE AND RUN ON YOUR FAVOURITE ARRAY.

where should i need to use it

1. when data is really small and there is only  5 to 10 element.

2. when data is small (10-20 items) but some items already sorted.

wrose time complexity=O(N2) comparing every single item with every item
best time = O(N)

average time would be O(N)