# 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);
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
```