# 1. Introduction

*Insertion Sort* is a simple and intuitive comparison-based sorting algorithm. It builds the final sorted array one item at a time. Think of it as playing cards: when you're dealt a hand in a card game, you might sort it by taking one card at a time and inserting it into its correct position within the sorted cards you hold.

# 2. Implementation Steps

1. Start from the second element (consider the first element as sorted).

2. Compare the current element with the previous elements.

3. If the current element is smaller than the previous element, compare it with the elements before the previous element.

4. Continue this process until the current element is greater than the element to its left or it reaches the start.

5. Insert the current element in its correct position in the sorted section.

# 3. Implementation in C++ Programming

```
#include<iostream>
void insertionSort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i]; // 2. Current element to be compared
int j = i - 1;
// 3. Move elements that are greater than key to one position ahead of their current position
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key; // 5. Insert key in its correct position
}
}
int main() {
int arr[] = {12, 11, 13, 5, 6};
int n = sizeof(arr) / sizeof(arr[0]);
insertionSort(arr, n);
std::cout << "Sorted array: \n";
for (int i = 0; i < n; i++) {
std::cout << arr[i] << " ";
}
std::cout << std::endl;
return 0;
}
```

### Output:

Sorted array: 5 6 11 12 13

### Explanation:

1. We consider the first element as already sorted, so we start with the second element.

2. This *key* element (or current element) is what we will insert into its correct position within the already sorted portion of the array.

3. Within the *while* loop, if the element to the left of the *key* (or *arr[j]*) is greater than the *key*, we shift *arr[j]* to the right.

4. We keep doing this shift operation until we find the correct position for our *key*.

5. Finally, we insert the *key* into its correct position.