Insertion sort is a type of sorting algorithms that works like the process of sorting playing cards, it divides the array into two parts, part of sorted numbers and other of unsorted numbers, the numbers that are in the wrong order ( numbers that exist in the unsorted part ) are inserted to the sorted part in the correct position.
|time Complexity||Space Complexity|
let's suppose we have an unsorted array [7,4,12,3],
the sorted part is 7 (bold styling), the unsorted part is from 4 to 3 (italic styling).
- (4 < 7) that's why we will insert 4 in the sorted part before 7 so the array will be [4,7,12,3]
- (12 > 7) therefore will keep it in the same position so the array will be [4,7,12,3]
- since 3 is smaller than 12,7 and 4, it will be in the first position, so the final array is [3,4,7,12]
if you're not familiar with python, you can find the implementaion of insertion sort algorithm in other programming languages:
def insertionSort(items: list) -> list: """ [ name ] => insertion sort [ type ] => sorting algorithms [ time complexity ] => O(n^2) [ space complexity ]=> O(1) [ params ] => (items) list to sort [ return ] => sorted list [ code reference link ] => ("https://www.geeksforgeeks.org/insertion-sort/") """ for i in range(1, len(items)): key = items[i] j = i - 1 while j >= 0 and key < items[j] : items[j + 1] = items[j] j -= 1 items[j + 1] = key return array
Special thanks to geeksforgeeks.
Have a good day :)