Hadron DaVinci

Insertion Sort Tutorial

30 Apr 2021 - Hadron DaVinci

Example

Sort the given array with Insertion Sort:

A = [5, 2, 4, 6, 1, 3]
insertion_sort(A)
assert(A) == [1, 2, 3, 4, 5, 6]

Method

1. Left swap repeatedly first number in unsorted space until
   
   • the first number is greater than number on its left
     
   • the first number has no left number
2. Reduce the unsorted space
3. repeat 1.and 2. until the unsorted space is empty

Complexity

Time Complexity: N^2
Space Complexity: 1
Stable

Code

method1.py