• 항상 두번째 요소를 왼쪽 요소와 비교해가면서 시작한다.
• Worst Case : 시간복잡도 O(n^2)
• Best Case : 시간복잡도 O(n)
• 버블정렬과 마찬가지로 in place 알고리즘으로 메모리를 절약할 수 있다.
• 자료의 개수가 많아지면 성능이 매우 떨어진다.

let insertionSort = (arr) => {
	// arr탐색
	// 1번째 인덱스부터 왼쪽과 비교하기 때문에 i는 1부터 시작
	for(let i=1; i<arr.length; i++) {
		// 현재변수는 i번째 인덱스의 값
		let curEl = arr[i];
		// left 변수는 i-1
		let left = i-1;

		// left가 0보다 크거나 같거나 arr[left]가 curEl보다 큰 경우 while문을 돌려준다.
		while(left >= 0 && arr[left] > curEl) {
			arr[left + 1] = arr[left];
			arr[left] = curEl;
			curEl = arr[left];
			left--;
		}
	}
	return arr;
}

let insertionSort = (arr) => {
	// arr탐색
	// 1번째 인덱스부터 왼쪽과 비교하기 때문에 i는 1부터 시작
	for(let i=1; i<arr.length; i++) {
		// 현재변수는 i번째 인덱스의 값
		let curEl = arr[i];
		// left 변수는 i-1
		let left = i-1;

		// left가 0보다 크거나 같거나 arr[left]가 curEl보다 큰 경우 while문을 돌려준다.
		while(left >= 0 && arr[left] > curEl) {
			arr[left + 1] = arr[left];
			left--;
		}
		// while문을 수행하면 left는 항상 -1이 되어서 빠져나오기 때문에 arr[left + 1]은 arr[0]번째가 된다.
		arr[left + 1] = curEl;
	}
	return arr;
}