- Assume the data to be sorted consists of two subsets S and U
Subset S : Sorted elements in the front partSubset U : Remaining elements not yet sorted
- Take elements one by one from the unsorted subset U and compare them starting from the last element of the already sorted subset S to find the position to insert.
- By repeating insertion sort, the elements of subset S increase one by one and the elements of subset U decrease one by one.
- When subset U becomes empty, insertion sort is complete
- O (n ^ 2)
- Because we need to compare elements of each subset every time!
arr = [69, 10, 30, 2, 16, 8, 31, 22]
N = len(arr)
for i in range(1,N): # 1 ~ N-1
tmp = arr[i]
print(arr[:i], arr[i:])
j = i -1
while j >= 0 and arr[j] > tmp:
arr[j+1] = arr[j]
j -= 1
arr[j+1] = tmp
print(arr)