Programming Puzzles: Python Edition

Background

Insertion sort is a simple sorting algorithm that builds the final sorted list one item at a time. It iterates through the input list, and for each element, it compares it to the elements that come before it and then inserts the element in the correct position. This process continues until all elements have been compared and placed in the correct position in the final sorted list.

It is called insertion sort because it can be thought of as inserting each element from the input list into its correct position in the final sorted list.

An example of insertion sort is sorting a deck of cards: starting with an empty left hand, we remove one card at a time from the deck with the right hand and place it in the correct position in the left ...