# Insert an element in a sorted array:

To insert an element in a sorted array, We have to start comparing the key element with the last element of the array and if the last element is greater than the key element then shift the last element to its next index. This procedure we have to follow until we find the element in array equal to or smaller than the key element.

like if we need to insert 5 in below array:

then we have to take a variable "i" and "i" will be initialized by array length - 1

So i = A.length - 1 = 5 - 1 = 4;

So 5 is compared with A[4], as A[4] is 8 so 8 > 5, then we have to shift A[i] to A[i+1],

A[i+1] = A[i] // A[5] = A[4] // A[5] = 8 and A[4] is empty.

and need to do --i, so i will be 3 now

now again we have to compare 5 with A[3], as A[3] is 7 and 7 > 5,

So again we have to shift it to the next index.

A[i+1] = A[i]; // A[4] = A[3] // A[4] = 7 and A[3] is empty.

--i; So i will be 2 now

now again we have to compare 5 with A[2], as A[2] is 6 and 6 > 5,

So again we have to shift it to the next index.

A[i+1] = A[i]; // A[3] = A[2] // A[3] = 6 and A[2] is empty.

--i; So i will be 1 now

now again we have to compare 5 with A[1], as A[1] is 4 and 4 < 5, now we have to stop and copy our key element to A[i+1] and A[i+1] is A[1+1] = A[2] and A[2] was empty, So we will insert our Key element to A[2] = 5, that's it.

# Program to insert an element in a sorted array is as below:

#include <iostream>

using namespace std;

/**

 * @brief The Array struct: Structure Which Contains array of size 10 and arrays

 * Length (number of items it contains.)

 */

struct Array

{

    int A[10];

    int iLength;

    int iSize;

};

void insertSort(struct Array &objArray, int iElement)

{

    int i = objArray.iLength - 1;

    /*

     *  If this condition is true, means array is full

     *  No other element can be inserted.

     */

    if (objArray.iLength == objArray.iSize)

        return;

    while ((objArray.A[i] > iElement) && (i >= 0))

    {

        objArray.A[i+1] = objArray.A[i];

        --i;

    }

    objArray.A[i+1] = iElement;

    objArray.iLength++;

}

void display(struct Array objArray)

{

    cout << "Elements in Array are: " << endl;

    for(int i = 0; i < objArray.iLength; ++i)

    {

        cout << objArray.A[i] << " " << endl;

    }

}

int main()

{

    Array objArr = {{2, 4, 6, 7, 8}, 5, 10};

    insertSort(objArr, 9);

    display(objArr);

    return 0;

}

# OutPut is as below:

You can also follow this link for more clarity.