# Insertion Sort Algorithm with C++ Code | Sorting Algorithms | Data Structures & Algorithms

In this tutorial we understand the working of insertion sort algorithm in data structures.

##### Insertion Sort –
• Insertion sort is a simple sorting algorithm that works the way we sort playing cards in our hands.
• Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time.
• Time Complexity: O(n*2)
• Efficient for (quite) small data sets, much like other quadratic sorting algorithms
• More efficient in practice than most other simple quadratic (i.e., O(n2)) algorithms such as selection sort or bubble sort
##### Working –
null
• Step 1 – Pick next element
• Step 2 – Compare with all elements in the sorted sub-list on the left
• Step 3 – Shift all the elements in the sorted sub-list that is greater than the
• value to be sorted
• Step 4 – Insert the value
• Step 5 – Repeat until list is sorted
##### Insertion Sort Algorithm –
1. declare variables – i, key, j
2. loop : i = 1 to n – 1 // outer loop
1. key = a[i] //pick the next element
2. j = i – j; // decrement j value
3. loop : (j>=0 && a[j]>key) // inner loop
1. arr[j+1] = arr[j]
2. j = j – 1
4. end loop // outer loop
5. arr[j+1] = key
3. end loop // outer loop