Insertion Sort

Published on 18 December 2018 (Updated: 02 February 2024)

Welcome to the Insertion Sort page! Here, you'll find a description of the project as well as a list of sample programs written in various languages.

This article was written by:

Jeremy Grifski
Ron Zuckerman

Description

Insertion sort is an algorithm that generally operates on a single list in place. It tracks a pointer that iterates through the list a single time, takes each item and inserts it sorted at the beginning of the list. At any given point all elements, from the beginning of the list up through the pointer, are in order. Once the pointer has iterated through the entire list, all elements have been inserted in order at the front of the list, and the list is now fully sorted.

Performance

The performance of sorting algorithms is generally defined in "Big O notation". If you are not familiar with such notations, please refer to the relevant article by Rob Bell or the Wikipedia entry listed in further readings below.

Cases	Big O Notatation
Best case	O(n)
Average case	O(n²)
Worst case	O(n²)

Although the main pointer of insertion sort only iterates through the list once it must also iterate through the existing sorted items at the beginning of the list every time an element is inserted. Thus the average case is O(n²), but so is the worst case.

Examples

In the examples below, each row inserts the element from the main pointer into the front of the list and moves the main pointer to the next element. The element in bold is the main pointer.

"4, 5, 3, 1, 2"

4 5 3 1 2
4 5 3 1 2
4 5 3 1 2
3 4 5 1 2
1 3 4 5 2
1 2 3 4 5

"3, 5, 4, 1, 2"

3 5 4 1 2
3 5 4 1 2
3 5 4 1 2
3 4 5 1 2
1 3 4 5 2
1 2 3 4 5

Requirements

Write a sample program that takes a list of numbers in the format "4, 5, 3, 1, 2". It should then sort the numbers and output them:

$ ./insertion-sort.lang "4, 5, 3, 1, 2"
1, 2, 3, 4, 5

The solution should handle duplicate elements

$ ./insertion-sort.lang "4, 5, 3, 1, 4, 2"
1, 2, 3, 4, 4, 5

In addition, there should be some error handling for situations where the user doesn't supply correct input.

Testing

Every project in the Sample Programs repo should be tested. In this section, we specify the set of tests specific to Insertion Sort. In order to keep things simple, we split up the testing as follows:

Insertion Sort Valid Tests
Insertion Sort Invalid Tests

Insertion Sort Valid Tests

Description	Input	Output
Sample Input	"4, 5, 3, 1, 2"	"1, 2, 3, 4, 5"
Sample Input: With Duplicate	"4, 5, 3, 1, 4, 2"	"1, 2, 3, 4, 4, 5"
Sample Input: Already Sorted	"1, 2, 3, 4, 5"	"1, 2, 3, 4, 5"
Sample Input: Reverse Sorted	"9, 8, 7, 6, 5, 4, 3, 2, 1"	"1, 2, 3, 4, 5, 6, 7, 8, 9"

Insertion Sort Invalid Tests

Description	Input
No Input
Empty Input	""
Invalid Input: Not A List	"1"
Invalid Input: Wrong Format	"4 5 3"

All of these tests should output the following:

Usage: please provide a list of at least two integers to sort in the format "1, 2, 3, 4, 5"

Articles

There are 18 articles: