Insertion Sort: Design and Implementation
A Programming and Interview Preparation Class by Edaqa Mortoray
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.
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 favourite 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:
def insertion_sort( items : List[ComparableT] ) -> List[ComparableT]:
Post your solution to get feedback. Feel free to ask questions.
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.
🎓 Levels: Beginner
Basic coding experience in any language required
⏱ Running Time: 23m
Edaqa is an avid teacher with many years of experience in programming and animation. Join the thousands of people who have already benefited from his writing, live streams, and videos.