Insertion Sort in Data Structure

What is Insertion Sort in Data Structure?

Insertion sort is a basic sorting algorithm that works by iteratively inserting each element of an unsorted list into the appropriate location in a sorted portion of the list. It is a stable sorting method, which means that elements with equal values remain in the same order in the sorted result.

Insertion Sort Algorithm

Insertion sort is a basic sorting algorithm that creates a sorted array one element at a time. It is classified as an "in-place" sorting method, which means it requires no additional memory space over the original array.

Working of Insertion Sort Algorithm

• Start with the second entry in the array, assuming the first is sorted.
• Compare the current element to the ones before it, switching as needed to ensure proper placement.
• Proceed to the next part and repeat the comparison and switching steps.
• Continue until the whole array is sorted.

When do you use the Insertion Sort algorithm?

Insertion sort is used when the number of elements is small. It can also be useful when the input array is nearly sorted, with only a few elements lost in a large array.

Complexity Analysis of Insertion Sort Algorithm

Time Complexity

Best Case Complexity

This occurs when no sorting is necessary, implying that the array is already sorted. The best-case time complexity for insertion sort is O(n).

Average Case Complexity

This arises when the array elements are jumbled and do not appropriately climb or descend. The average case time complexity for insertion sort is O(n2).

Worst Case Complexity

This occurs when array members must be sorted in reverse order. That is, assume you need to sort the array elements in ascending order but the elements are in descending order. The worst-case temporal complexity for insertion sort is O(n2).

Space Complexity

The selection sort algorithm's space complexity is O(1).

Applications of Insertion Sort Algorithm

• Small datasets: Efficient for small input sizes; faster than Merge Sort or Quick Sort.
• Partially Sorted Arrays: Sorts the remaining unsorted elements in partially sorted arrays.
• Online Algorithms: Sort lists as new data comes, making them handy for real-time sorting.
• Adaptive Sorting: Adapts quickly to changes in input data and is most efficient for almost sorted arrays.
• In-Place Sorting: Sorts data without using additional memory, making it perfect for huge datasets.

Advantages of Insertion Sort Algorithm

• Easy Implementation: When compared to complex algorithms such as quick sort or merge sort, this algorithm is simple to understand and implement.
• Space Efficiency: Requires little space with a complexity of O(1); no additional memory is required.
• Adaptive: Performs well with partially sorted arrays, resulting in faster sorting times.
• Online Sorting: Online sorting sorts data as it is received, making it suitable for continuous data streams or real-time processing.
• Best for small arrays: Optimal for tiny arrays because of its simplicity and quickness.
• Stable: Maintains the relative order of equal elements throughout sorting.

Disadvantages of Insertion Sort Algorithm

• Inefficient for large lists: The worst-case complexity of O(n^2) restricts performance.
• Not Parallelizable: The sequential nature makes parallel processing difficult.
• Less Efficient: For large lists, techniques such as merge sort and rapid sort outperform with O(n log n) complexity.

Boundary Cases for the Insertion Sort Algorithm

When the number of elements is small, the insertion sort method is used. It can also be beneficial when the input array is nearly sorted, with only a few elements lost in a large array.