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:
<a href ="https://github.com/mortoray/interview.codes/tree/master/insertion-sort" target="_blank">github.com</a>

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:

<pre><code>```py
def insertion_sort( items : List[ComparableT] ) -> List[ComparableT]:
```</code></pre>



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.

Insertion Sort: Design and Implementation

Back End

Interview Prep: Insertion Sort

Description for Insertion Sort: Design and Implementation