public void insertionSort(Integer[] arr) {

for(int i = 1; i < arr.length; i++) {

int key = arr[i];

int k = i-1;

while(key < arr[k]) {

arr[k+1] = arr[k];

k--;

if(k < 0)

break;

}

arr[k+1] = key;

}

}