public void insertionSort(int[] array){
  for(int i = 1;i<array.length;i++){
     int cur = array[i];
     int insertionIndex = i-1;
    while(insertionIndex >= 0&&array[insertionIndex]>cur){
      array[insertionIndex+1] = array[insertionIndex];
      insertionIndex--;
    }      
    array[insertionIndex+1] = cur;
  }  
}