Sorting
Insertion sort is a straightforward, well-performing sort algorithm. While it has O(n²) runtime (rather than O(n log n), like Quicksort and Mergesort), it is often faster for smaller, close-to-already sorted lists, because of the way the algorithm works.
Read about Insertion sort at https://en.wikipedia.org/wiki/Insertion_sort, paying close attention to the description of the algorithm.
We’ve given you a file, insertionsort.py, with a function, insertion_sort:
def insertion_sort(alist):
"""Given a list, sort it using insertion sort."""
Implement this function.
Shell sort
There’s a further algorithm, Shell sort, which performs iterative insertion sorts over spans. It’s also technically O(n²) but is typically several times faster Insertion sort—while still having the ease-of-implementation of Insertion sort.