Insertion Sort

Algorithm Steps

Start from the second element (index 1) of the array.
Set the current element as the key.
Compare the key with the elements before it.
Shift all elements that are greater than the key one position to the right.
Insert the key into its correct position.
Repeat the process for all elements until the array is sorted.

Insertion Sort Program Code

Python

Java

JavaScript

C++

Kotlin

Swift

Php

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

if __name__ == '__main__':
    arr = [6, 3, 8, 2, 7, 4]
    insertion_sort(arr)
    print("Sorted array is:", arr)