Insertion Sort

Insertion Sort is a simple, comparison-based sorting algorithm that builds the final sorted array one element at a time. It takes each element from the unsorted part and slides it into its correct position in the sorted part. It is like placing a new card in the right spot of a sorted hand, making it intuitive and efficient for small dataset, especially for partially sorted lists.

Things to Observe

• Inserting into Place: Watch how each element is picked from the unsorted part and slides into its correct position in the sorted part on the left.
• Adaptive Performance: Try visualizing a nearly sorted list. You'll notice Insertion Sort runs much faster because it only has to shift a few elements for each insertion. This makes it very efficient for lists that are already mostly sorted.

Pseudocode

for i = 1 to (n - 1):

    key = arr[i]

    j = i - 1

    while j >= 0 and arr[j] > key:

        arr[j + 1] = arr[j]

        j = j - 1

    arr[j + 1] = key