Insertion Sort

Ever organized a hand of playing cards? Then you already know Insertion Sort! This algorithm 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.

    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