# Insertion Sort in Data Structures - Infovistar

### Insertion Sort

Insertion sort works similar to the sorting of playing cards in hands. In the card game, it is assumed that the first card is already sorted, and then we select an unsorted card.

It will be placed at the right side if the unsorted card is greater than the first; otherwise, it will be placed at the left side. A similar procedure is followed for all unsorted cards.

Insertion sort follows the same approach. In the insertion sort, the idea is to take one element and iterate through the array of elements that are sorted in ascending or descending order.

It is simple to use, but not recommended for large data sets, because time complexity of insertion sort in the average case and worst case is `O(n2)`, where n is the number of elements.

It is less efficient than other sorting algorithms such as heap sort, quick sort, merge sort, etc.

### Time Complexity

Case Time Complexity
Best Case O(n)
Average Case O(n2)
Worst Case O(n2)
• Best Case O(n):It occurs when there is no sorting needed, i.e. the array is already sorted.
• Average Case O(n): The array elements are in a jumbled order that is not properly ascending and descending.
• Worst Case O(n): This occurs when the array elements need to be sorted in reverse order. In other words, suppose you have to sort an array in ascending order, but its elements are arranged in descending order.

### Space Complexity

 Space Complexity O(1) Stable Yes
• A insertion sort required extra variables for swapping. Hence, the space complexity of insertion sorting is `O(1)`.