Insertion Sort
by 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."");
  }
}