1. Thuật toán:

• Duyệt từ phần tử thứ 2 đến cuối mảng.
• Nếu phần tử được duyệt nhỏ hơn phần tử trước (bên trái), dịch nó dần về bên trái cho đến khi nó lớn hơn phần tử bên trái.

2. Minh họa:

3. Code Python:

def insertionSort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

4. Độ phức tạp thuật toán:

• Best: $\Omega(n) = n$

• Avarage: $\Theta (n) = n^2$

• Worst: $\Omicron(n) = n^2$