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.

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.

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.

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 |

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