Choose a key, starting from index to , where is the length of the array.
Keep swapping the key with all the larger values on its left side until a value less than or equal to the key occurs, or index is reached.
Select the next index as the key. Repeat step 2.
def insertion_sort(arr): for i in range(1, len(arr)): # Set key: key = arr[i] j = i - 1 while j >= 0 and arr[j] > key: # Swap: arr[j + 1] = arr[j] arr[j] = key # Decrement 'j': j -= 1 return arr array = [5, 2, 12, 12, 1] print("Original array: %s" % array) print("Sorted array: %s" % insertion_sort(array))
RELATED TAGS
View all Courses