insertion_sort.py

def insertion_sort(input_list: list) -> list:
    """Sort a list with insertion sort algorithm.
    :param input_list:  a list to be sorted.    
    :type input_list: list    
    :return: sorted list in ascending order.    
    :rtype: list    
    """    
    # Check if need to sort    
    if input_list == [] or len(input_list) == 1:
        return input_list
    else:
        # Create a tmporary list to hold middle steps        
        tmp = []
        # Pick one element        
        for picked_element in input_list:
            # Check length            
            length = len(tmp)
            if length == 0:
                tmp.append(picked_element)
            else:
                # Scan tmp list to find position to insert                
                # Use var inserted to determine if need to append                
                inserted = False                
                for potential_position in range(length):
                    # Right position found                    
                    if tmp[potential_position] > picked_element:
                        tmp.insert(potential_position, picked_element)
                        inserted = True                        
                        break                
                        # All existing elements are smaller, no insertion happends,                
                        # just append at the end                
                        if not inserted:
                    tmp.append(picked_element)
        return tmp