A Collection of Code Snippets in as Many Programming Languages as Possible

This project is maintained by TheRenegadeCoder

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

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.

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^{2}) |

Worst case | O(n^{2}) |

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^{2}), but so
is the worst case.

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 - 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 4 5
**1**2 - 1 3 4 5
**2** - 1 2 3 4 5

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.

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

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" |

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"
```

- Insertion Sort in Algol68
- Insertion Sort in C
- Insertion Sort in C#
- Insertion Sort in C++
- Insertion Sort in Euphoria
- Insertion Sort in Go
- Insertion Sort in Haskell
- Insertion Sort in Java
- Insertion Sort in Javascript
- Insertion Sort in Mathematica
- Insertion Sort in Matlab
- Insertion Sort in Perl
- Insertion Sort in Php
- Insertion Sort in Python
- Insertion Sort in Rust