Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. However, insertion sort provides several advantages: Simple implementation: Jon Bentley shows a three-line c version, and a five-line optimized version Efficient for (quite) small data sets, much like other quadratic sorting algorithmsAdaptive, i.e., efficient for data sets that are already substantially sorted: the time complexity is O(kn) when each component in the input is no more than K places away from its sorted position Stable; i.e., makes not change the relative order of components with equal keys
To perform an insertion sort, begin at the left-most component of the array and invoke insert to insert each component encountered into its correct position. It operates by beginning at the end of the sequence and shifting each component one place to the right until a suitable position is found for the new component.
""" A recursive implementation of the insertion sort algorithm """ from typing import List def rec_insertion_sort(collection: List, n: int): """ Given a collection of numbers and its length, sorts the collections in ascending order :param collection: A mutable collection of comparable elements :param n: The length of collections >>> col = [1, 2, 1] >>> rec_insertion_sort(col, len(col)) >>> print(col) [1, 1, 2] >>> col = [2, 1, 0, -1, -2] >>> rec_insertion_sort(col, len(col)) >>> print(col) [-2, -1, 0, 1, 2] >>> col =  >>> rec_insertion_sort(col, len(col)) >>> print(col)  """ # Checks if the entire collection has been sorted if len(collection) <= 1 or n <= 1: return insert_next(collection, n - 1) rec_insertion_sort(collection, n - 1) def insert_next(collection: List, index: int): """ Inserts the '(index-1)th' element into place >>> col = [3, 2, 4, 2] >>> insert_next(col, 1) >>> print(col) [2, 3, 4, 2] >>> col = [3, 2, 3] >>> insert_next(col, 2) >>> print(col) [3, 2, 3] >>> col =  >>> insert_next(col, 1) >>> print(col)  """ # Checks order between adjacent elements if index >= len(collection) or collection[index - 1] <= collection[index]: return # Swaps adjacent elements since they are not in ascending order collection[index - 1], collection[index] = ( collection[index], collection[index - 1], ) insert_next(collection, index + 1) if __name__ == "__main__": numbers = input("Enter integers separated by spaces: ") numbers = [int(num) for num in numbers.split()] rec_insertion_sort(numbers, len(numbers)) print(numbers)