# Insertion Sort – Data Structure and Algorithm

Insertion sort functions as a straightforward sorting algorithm, resembling the manner in which you arrange playing cards in your hands. It virtually divides the array into two segments: one sorted and the other unsorted. From the unsorted portion, it selects values and positions them accurately within the sorted segment. This process keeps continuing with each iteration until the array becomes fully sorted. Additionally, this method’s efficiency improves when implemented with small datasets, making it an effective option for sorting tasks.

## Insertion Sort Algorithm

For ascending order sorting of an array with a size of N, initially, begin by iterating through the array. Compare the current element (referred to as the key) with the element that comes before it. If the key element happens to be smaller than its predecessor, subsequently proceed to compare it with the elements that precede it. In such cases, shift the larger elements one position upward so as to generate room for the swapped element. This series of comparisons and element shifts ensures that the array becomes sorted in ascending order.

## Working of the algorithm

Consider the following example:

Example Array: arr[] = {25, 18, 5, 32, 14, 7}

This example illustrates the step-by-step demonstration of the insertion sort algorithm, showcasing how each pass rearranges the array into ascending order.

## Complexity Analysis

### Time Complexity of Insertion Sort

• Worst-case time complexity of the Insertion sort is O(N^2)
• Average case time complexity of the Insertion sort is O(N^2)
• Best case time complexity of the Insertion sort is O(N).

### Space Complexity of Insertion Sort

The auxiliary space complexity of Insertion Sort is O(1)

In conclusion, the insertion sort algorithm stands as a valuable sorting technique. By systematically comparing and shifting elements, it ensures the arrangement of data in ascending order. This method’s efficiency is evident through its straightforward implementation and effectiveness, especially with smaller datasets. Consequently, insertion sort serves as a foundational sorting approach, simplifying the organization of data for a wide range of applications.