Insertion Sort Visualization

DESCRIPTION

Insertion Sort is a **simple and efficient comparison-based sorting algorithm** that builds the sorted array one element at a time by inserting each element into its correct position. It works similarly to how we sort playing cards in our hands.

The algorithm starts with the second element and compares it with the previous elements, shifting larger elements to the right and inserting the current element in its correct position. This process is repeated for each element until the entire array is sorted.

Unlike Selection Sort, Insertion Sort performs well on **small or nearly sorted datasets**. It has a **time complexity of O(n²)** in the worst and average cases but performs in **O(n) time for nearly sorted data**, making it more efficient in such scenarios.

A key advantage of Insertion Sort is that it is **stable**, meaning equal elements retain their original relative positions after sorting. It is also an **in-place sorting algorithm**, requiring no extra memory.

Due to its efficiency in handling small or nearly sorted datasets, Insertion Sort is often used in hybrid sorting algorithms like Timsort and as a helper function in more complex sorting techniques.