Introduction

Insertion Sort Technique: Insertion Sort is a simple sorting algorithm that builds the sorted list one element at a time by repeatedly taking an unsorted element and placing it into its correct position within the sorted portion of the array.
This technique gets its name because elements are "inserted" into their correct position as the array is traversed.

How can we sort an array?

• In Insertion Sort, we start with the first element, considering it already sorted.
• For each subsequent element, we compare it with the sorted portion of the array.
• If an element is smaller than elements in the sorted section, we shift the larger elements to the right to make space for the current element.
• We place the current element into its correct position within the sorted portion.
• This process continues until the entire array is sorted.

Important Observations

• In the first pass, the second element is placed relative to the first element.
• In the second pass, the third element is inserted into its correct position within the first two elements.
• In the third pass, the fourth element is placed relative to the first three elements.
• This process continues until all elements are sorted.
• The array will be sorted in ascending order.

Key Characteristics:

• Iterative and comparison-based sorting technique.
• In-place sorting; no additional space required.
• Stable algorithm (preserves order of equal elements).
• Efficient for small or nearly sorted datasets.

Advantages:

• Simple to understand and implement.
• Efficient for small datasets or nearly sorted data.
• Does not require additional memory space.

Disadvantages:

• Not efficient for large datasets.
• Time complexity is (O(n^2)) in the average and worst cases.
• Slower compared to advanced sorting techniques like Quick Sort or Merge Sort.

Time Complexity:

• Best Case: (O(n)) (nearly sorted list).
• Average Case: (O(n^2)).
• Worst Case: (O(n^2)).