InsertionSort.md (1450B)
1 # Insertion Sort 2 3 CRLS 2.1 4 5 **Definition:** Insertion sort is a sorting algorithm with a worst case complexity of n^2 that selects the next element in the array, moves it to the left side in the correctly sorted position, and then iterates through the list for all items. 6 7 This can be thought of as sorting cards by hand. You start with all cards in the right hand. You then remove the first card and place it in the left hand. You then do the same thing for the next card in the right hand placing it in the sorted location. You continue this until are cards are in the left hand. 8 9 The only issue with this analogy is that insertion sort uses only one array instead of two where you track the sorted part of the array and as elements are added all elements to the right are pushed over until reaching the spot where it was formerly. 10 11 Implementation in python: 12 13 ```python3 14 def insertion_sort(ls): 15 sortedLen = 0 16 for i in range(0, len(ls)): 17 x = sortedLen 18 added = False 19 while x >= 0: 20 if ls[x] < ls[i]: 21 move_and_offset(i, x + 1, ls) 22 added = True 23 break 24 x -= 1 25 if added == False: 26 move_and_offset(i, 0, ls) 27 sortedLen += 1 28 return ls 29 30 def move_and_offset(posFrom, posTo, ls): 31 last = ls[pos From] 32 i = posTo 33 while i < posFrom + 1: 34 temp = ls[i] 35 ls[i] = last 36 last = temp 37 i+=1 38 ```