# Insertion Sortby Isai Damier, Android Engineer @ Google

```/***************************************************************************
* Author: Isai Damier
* Title: Insertionsort
* Project: geekviewpoint
* Package: algorithms
*
* Statement:
*   Given a disordered list of integers (or any other items),
*   rearrange the integers in natural order.
*
* Sample Input: {8,5,3,1,9,6,0,7,4,2,5}
* Sample Output: {0,1,2,3,4,5,5,6,7,8,9}
*
* Time Complexity of Solution:
*   Best O(n); Average O(n^2); Worst O(n^2).
*
* Approach:
*   Insertion sort is good for collections that are very small
*   or nearly sorted. Otherwise it's not a good sorting algorithm:
*   it moves data around too much. Each time an insertion is made,
*   all elements in a greater position are shifted.
**************************************************************************/
public void insertionsort(int[] input) {
for (int i = 1, k, tmp; i < input.length; i++) {
tmp = input[i];
for (k = i; k > 0 && tmp < input[k - 1]; k--) {
input[k] = input[k - 1];
}
input[k] = tmp;
}
}```
```import org.junit.Test;
import static org.junit.Assert.*;

public class SortingTest {

/**
* Test of insertionsort method, of class Sorting.
*/
@Test
public void testInsertionsort() {
System.out.println(""insertionsort"");
int[] input = null;
Sorting instance = new Sorting();
instance.insertionsort(input);
fail(""The test case is a prototype."");
}
}```