Insertion Sort is a simple and intuitive sorting algorithm that builds a sorted array one element at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, it has several advantages, including simplicity, efficiency for small datasets, and stability.

How Insertion Sort Works:

1. Start from the second element (index 1) of the array.
2. Compare the current element with the elements in the sorted portion (to its left).
3. Shift all larger elements in the sorted portion one position to the right to make space for the current element.
4. Insert the current element into its correct position in the sorted portion.
5. Repeat this process for all elements in the array until the entire array is sorted.

Complexity Analysis:

• Time Complexity: O(n²) in the worst and average cases, O(n) in the best case (when the array is already sorted).
• Space Complexity: O(1) (in-place sorting).

Characteristics:

• Insertion Sort is stable.
• It is an in-place sorting algorithm.
• Efficient for small datasets and partially sorted arrays.
• The graph describing the Insertion Sort time complexity looks like this: