Insertion Sort is a simple sorting algorithm that works efficiently for small data sets or data that is already partially sorted. It is a comparison-based sorting algorithm that builds the final sorted array one element at a time. In this article, we will explore how Insertion Sort works in the context of data structures using the C programming language.

## What Is Insertion Sort?

Insertion Sort is an in-place sorting algorithm, which means it rearranges the elements within the array without requiring any additional data structures. The algorithm divides the input array into two parts: a sorted subarray and an unsorted subarray. Initially, the sorted subarray consists of only one element – the first element of the input array.

The algorithm then iterates through the unsorted subarray, comparing each element with the elements in the sorted subarray and inserting it at its correct position. This process continues until all elements from the unsorted subarray are inserted into their correct positions in the sorted subarray, resulting in a fully sorted array.

## How Does Insertion Sort Work?

The working of Insertion Sort can be explained using an example. Consider an array **[5, 3, 8, 1, 2]**. Initially, this array can be divided into a sorted subarray **[5]** and an unsorted subarray **[3, 8, 1, 2]**.

The algorithm starts by considering the first element from the unsorted subarray (**3**) and compares it with elements from the sorted subarray (**[5]**). Since __3__ is smaller than __5__, it is inserted before __5__, resulting in a new sorted subarray of **[3, 5]** and an unsorted subarray of **[8, 1, 2]**.

Next, the algorithm considers the next element from the unsorted subarray (**8**) and compares it with elements from the sorted subarray (**[3, 5]**). Since __8__ is greater than all the elements in the sorted subarray, it remains at its current position. The sorted subarray remains unchanged as **[3, 5]**, and the unsorted subarray becomes **[1, 2]**.

The algorithm continues this process for each element in the unsorted subarray until there are no more elements left. After inserting all elements into their correct positions, the final sorted array will be **[1, 2, 3, 5, 8]**.

## Implementation of Insertion Sort in C

In C programming language, we can implement Insertion Sort using a simple loop structure. Here is an example implementation:

```
#include <stdio.h>
void insertionSort(int arr[], int n) {
int i, key, j;
for (i = 1; i < n; i++) {
key = arr[i];
j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
int main() {
int arr[] = {5, 3, 8, 1, 2};
int n = sizeof(arr) / sizeof(arr[0]);
insertionSort(arr, n);
printf("Sorted array: ");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
return 0;
}
```

In this example, we define a function **insertionSort** that takes an array **arr** and its length **n**. The function uses a loop to iterate through each element of the array and perform the necessary comparisons and insertions to sort the array in ascending order.

We then call the **insertionSort** function in the **main** function, passing our example array and its length. Finally, we print the sorted array using a loop.

## Conclusion

In conclusion, Insertion Sort is a simple yet efficient sorting algorithm that can be used for small data sets or partially sorted data. Its in-place nature makes it memory-efficient, as it does not require any additional data structures. By dividing the input array into a sorted subarray and an unsorted subarray, Insertion Sort iteratively inserts each element from the unsorted subarray at its correct position in the sorted subarray until all elements are sorted.

By understanding how Insertion Sort works and implementing it in C programming language, you can effectively sort arrays and gain a deeper understanding of sorting algorithms in general.