Insertion Sort in Every Language

Published on 16 December 2018 (Updated: 16 December 2018)

Insertion Sort in Every Language

In this article, we’ll tackle Insertion Sort, an inefficient sorting algorithm.

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.

   
Best case O(n)
Average case O(n2)
Worst case O(n2)

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(n2), 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”

“3, 5, 4, 1, 2”

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

The following table contains various test cases that you can use to verify the correctness of your solution:

Description Input Output
No Input   Usage: please provide a list of at least two integers to sort in the format “1, 2, 3, 4, 5”
Empty Input ”” Usage: please provide a list of at least two integers to sort in the format “1, 2, 3, 4, 5”
Invalid Input: Not a list 1 Usage: please provide a list of at least two integers to sort in the format “1, 2, 3, 4, 5”
Invalid Input: Wrong Format 4 5 3 Usage: please provide a list of at least two integers to sort in the format “1, 2, 3, 4, 5”
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

Articles

Further Readings