Insertion sort builds a sorted list one item at a time. It's much less efficient on large lists than merge sort because it's O(n^2), but it's actually faster (not in Big O terms, but due to smaller constants) than merge sort on small lists.
Click to play video
Our influencers want to sort their affiliate deals by revenue. None of our users have more than a couple hundred affiliate deals, so we don't need an n * log(n) algorithm like merge sort. In fact, insertion_sort can be faster than merge_sort, and uses less of our server's memory.
Complete the insertion_sort function according to the given pseudocode:
j variable to the current indexj is greater than 0 and the element at index j-1 is greater than the element at index j:
j and j-1j by 1In some languages you need to use a temp variable to swap values, but in python you can do that in a single line:
a = 5
b = 3
a, b = b, a
print(a)
# 3
print(b)
# 5