Insertion sort

Efficient for small lists, with size less then 30.

Special cases are:

• if list is almost sorted, it will be near linear time
• if sorted list is reversed, it will be quadratic time

Java

C#