// your code goes here
 
function insertionSort(arr, n) {
	for(let i=1;i<n;i++) {
		let key_element = arr[i];
		let j = i-1;
 
		while(j>=0 && arr[j] > key_element){
			arr[j+1] = arr[j];
			j--;
		}
		arr[j+1] = key_element;
	}
	return arr;
}
 
console.log(insertionSort([5, 6, 1, 8, 4], 5))
 
// [5, 6, 1, 8, 4]
 
// i=2, key_element = 1
 
// j=1, arr[j] > 1, [5, 6, 6, 8, 4]
// j=0, arr[j] > 1, [1, 5, 6, 8, 4]
// j=-1
 
// arr[j+1] = key_element;

Ly8geW91ciBjb2RlIGdvZXMgaGVyZQoKZnVuY3Rpb24gaW5zZXJ0aW9uU29ydChhcnIsIG4pIHsKCWZvcihsZXQgaT0xO2k8bjtpKyspIHsKCQlsZXQga2V5X2VsZW1lbnQgPSBhcnJbaV07CgkJbGV0IGogPSBpLTE7CgkJCgkJd2hpbGUoaj49MCAmJiBhcnJbal0gPiBrZXlfZWxlbWVudCl7CgkJCWFycltqKzFdID0gYXJyW2pdOwoJCQlqLS07CgkJfQoJCWFycltqKzFdID0ga2V5X2VsZW1lbnQ7Cgl9CglyZXR1cm4gYXJyOwp9Cgpjb25zb2xlLmxvZyhpbnNlcnRpb25Tb3J0KFs1LCA2LCAxLCA4LCA0XSwgNSkpCgovLyBbNSwgNiwgMSwgOCwgNF0KCi8vIGk9Miwga2V5X2VsZW1lbnQgPSAxCgovLyBqPTEsIGFycltqXSA+IDEsIFs1LCA2LCA2LCA4LCA0XQovLyBqPTAsIGFycltqXSA+IDEsIFsxLCA1LCA2LCA4LCA0XQovLyBqPS0xCgovLyBhcnJbaisxXSA9IGtleV9lbGVtZW50Ow==