// your code goes here
 
function insertionSort(arr, n) {
	for(let i=1;i<n;i++){ // n-1
		let key_element = arr[i];
 
		// move the larger elements than arr[i] occuring before i one place ahead
		// place arr[i] at the vacant position created
		let j = i-1; // assuming that j+1 is the vacant position of arr[i]
		while(j>=0 && arr[j]>key_element) {
			arr[j+1] = arr[j];
			j--;
		}
		// j+1 is the correct position of arr[i]
		arr[j+1] = key_element;
	}
	return arr;
}
 
console.log(insertionSort([1, 3, 4, 5, 2], 5))

Ly8geW91ciBjb2RlIGdvZXMgaGVyZQoKZnVuY3Rpb24gaW5zZXJ0aW9uU29ydChhcnIsIG4pIHsKCWZvcihsZXQgaT0xO2k8bjtpKyspeyAvLyBuLTEKCQlsZXQga2V5X2VsZW1lbnQgPSBhcnJbaV07CgkJCgkJLy8gbW92ZSB0aGUgbGFyZ2VyIGVsZW1lbnRzIHRoYW4gYXJyW2ldIG9jY3VyaW5nIGJlZm9yZSBpIG9uZSBwbGFjZSBhaGVhZAoJCS8vIHBsYWNlIGFycltpXSBhdCB0aGUgdmFjYW50IHBvc2l0aW9uIGNyZWF0ZWQKCQlsZXQgaiA9IGktMTsgLy8gYXNzdW1pbmcgdGhhdCBqKzEgaXMgdGhlIHZhY2FudCBwb3NpdGlvbiBvZiBhcnJbaV0KCQl3aGlsZShqPj0wICYmIGFycltqXT5rZXlfZWxlbWVudCkgewoJCQlhcnJbaisxXSA9IGFycltqXTsKCQkJai0tOwoJCX0KCQkvLyBqKzEgaXMgdGhlIGNvcnJlY3QgcG9zaXRpb24gb2YgYXJyW2ldCgkJYXJyW2orMV0gPSBrZXlfZWxlbWVudDsKCX0KCXJldHVybiBhcnI7Cn0KCmNvbnNvbGUubG9nKGluc2VydGlvblNvcnQoWzEsIDMsIDQsIDUsIDJdLCA1KSk=