Hackbright Code Challenges

Insertion Sort

Insertion Sort

Whiteboard

Harder

Challenge

Medium

Concepts

Sorting

Download

insertion-sort.zip

Solution

Insertion Sort: Solution


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.