// your code goes here
 
function insertionSort(arr, n) {
	for(let i=1;i<n;i++){
		let key_element = arr[i];
		let j = i-1;
 
		// Move all the elements in range from 0 to i-1
		// one position ahead if they are greater than key_element
 
		while(j>=0 && arr[j]>key_element) {
			arr[j+1] = arr[j];
			j--;
		}
		arr[j+1] = key_element;
	}
	return arr;
}
 
// [6, 3, 4, 2, 1]
 
// key_element = 3, i=1
// 	j=0, arr[j] > key, arr[j+1] = 6
// 	j=-1, [6, 6, 4, 2, 1]
 
 
console.log(insertionSort([6, 3, 4, 2, 1], 5))

Ly8geW91ciBjb2RlIGdvZXMgaGVyZQoKZnVuY3Rpb24gaW5zZXJ0aW9uU29ydChhcnIsIG4pIHsKCWZvcihsZXQgaT0xO2k8bjtpKyspewoJCWxldCBrZXlfZWxlbWVudCA9IGFycltpXTsKCQlsZXQgaiA9IGktMTsKCQkKCQkvLyBNb3ZlIGFsbCB0aGUgZWxlbWVudHMgaW4gcmFuZ2UgZnJvbSAwIHRvIGktMQoJCS8vIG9uZSBwb3NpdGlvbiBhaGVhZCBpZiB0aGV5IGFyZSBncmVhdGVyIHRoYW4ga2V5X2VsZW1lbnQKCQkKCQl3aGlsZShqPj0wICYmIGFycltqXT5rZXlfZWxlbWVudCkgewoJCQlhcnJbaisxXSA9IGFycltqXTsKCQkJai0tOwoJCX0KCQlhcnJbaisxXSA9IGtleV9lbGVtZW50OwoJfQoJcmV0dXJuIGFycjsKfQoKLy8gWzYsIDMsIDQsIDIsIDFdCgovLyBrZXlfZWxlbWVudCA9IDMsIGk9MQovLyAJaj0wLCBhcnJbal0gPiBrZXksIGFycltqKzFdID0gNgovLyAJaj0tMSwgWzYsIDYsIDQsIDIsIDFdCgoKY29uc29sZS5sb2coaW5zZXJ0aW9uU29ydChbNiwgMywgNCwgMiwgMV0sIDUpKQ==