Interview Prep: Insertion Sort

Description

Insertion sort is a commonly taught algorithm, and some interviewers like to ask about it. As you'll see in this class, it's an easy algorithm to understand and implement. You'll learn the algorithmic complexity and understand why the algorithm is rarely used.

I'll give a walkthrough of the source code, which I also provide in my repository: github.com

Also watch my course on Binary Search, insertion sort makes use of that algorithm.

Project

I want you to write an insertion sort function. Choose your favorite language, or the one for your interview, and implement a function that sorts a list of values. Use the algorithm I present in this class.

In the example Python implementation, the signature looks like this:

```py
def insertion_sort( items : List[ComparableT] ) -> List[ComparableT]:
```

Verify Sort Algorithm

As a bonus project, write the verify sort algorithm. This is an essential bit of code for unit tests. It also explores concepts that will help you during your interviews.

Verify sort takes an unsorted list and a sorted list. It verifies that the sorted list is indeed the sorted version of the unsorted one.