한번에 한 원소씩 정렬된 배열을 만들어가는 알고리즘.
처음 두 원소의 정렬이 끝나면 다음엔 세번째 원소와의 비교를 계속한다.
크기가 작은 배열이라면 선택정렬, 버블 정렬 보다 성능이 우수하다.
const insertionSort = array => {
let length = array.length, j, temp;
for(let i = 1; i < length; i++){
j = i;
temp = array[j]
while(j > 0 && array[j-1] > temp){
array[j] = array[j-1];
j--;
}
array[j] = temp;
}
}