Insertion sort using vectors, not working

Question

Im trying to create an insertion sort algorithm using vectors, but instead of parsing the elements from the start of the array (vector here), i tried doing it from the end. The code does nothing but sort the element for the first time, and delete the first element of my vector. I want to know what correction to my code can I make for this to work. Basic procedure:

1. Start by element towards last (second last element)
2. Insert it in correct position in the 'sorted' subarray (vector) after it
3. Delete it from its initial position
4. Continue with algorithm, traversing backwards until vector's beginning

Code:

#include <iostream>
#include <vector>
using namespace std;

template <class T>
void isort(vector <T> &ar){
    //start from second last element upto first element
    for(auto i = ar.end()-2; i >= ar.begin(); i--){
        //iterator pointing towards element next to insertion element
        auto j = i + 1;
        //traverse and increase the pointer until condition met
        while(j != ar.end() && *i < *j) j++;
        //insert the insertion element at final position of the pointer
        ar.insert(j,*i);
        //erase the original element
        ar.erase(i);
    }
}
template <class T>
void display(vector <T> &ar){
    for(auto i = ar.begin(); i != ar.end(); i++){
        cout << *i << ' ';
    }
    cout << endl;
}
int main() {
    vector <int> X {6,1,7,1,3,2,6723,4,1,6};
    display <int>(X);
    isort <int>(X);
    display <int>(X);
}

Expected output:

6 1 7 1 3 2 6723 4 1 6 
1 1 1 2 3 4 6 6 7 6723

Output attained:

6 1 7 1 3 2 6723 4 1 6 
1 7 1 3 2 6723 4 1 6 1 

Answer 1

About your way, so I modified a bit your code according to your solution, so it works now. The performance might be even worse than swapping, just because vector shifts elements after insert/erase.

#include <iostream>
#include <vector>
using namespace std;

template <class T>
void isort(vector <T>& ar) {
    if (ar.size() < 2)
        return;

    //start from second last element upto first element
    auto i = ar.end() - 2;
    do
    {
        //iterator pointing towards element next to insertion element
        auto j = i + 1;
        //traverse and increase the pointer until condition met
        while (j != ar.end() && *i > *j) ++j;
        //insert the insertion element at final position of the pointer

        if (*(j - 1) < *i && (j - 1) != i) {
            ar.insert(j, *i);
            i = ar.erase(i);
        }

        if (i == ar.begin())
            break;
        --i;
    } while (true);
}

template <class T>
void display(vector <T> &ar){
    for(auto i = ar.begin(); i != ar.end(); i++){
        cout << *i << ' ';
    }
    cout << endl;
}
int main() {
    vector <int> X {6,1,7,1,3,2,6723,4,6,1};
    X.reserve(X.size() * 2);
    display <int>(X);
    isort <int>(X);
    display <int>(X);
}