DEV Community

Clean Code Studio
Clean Code Studio

Posted on • Updated on

Insertion Sort (Python Algorithms)

Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort.

def insertion_sort(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
    return arr
Enter fullscreen mode Exit fullscreen mode

The time complexity of insertion sort is O(n^2).

Sorting Algorithms
Insertion Sorting Algorithm

Python Insertion Sorting Algorithm

Top comments (0)