삽입 정렬

시간 복잡도: O(N^2)
기본 배열의 정렬 상태에 따라 소요 시간이 크게 바뀜
-> 모든 데이터를 검사하는 것이 아니라 정렬 도중에 본인보다 작은 데이터를 만나면 해당 원소의 정렬을 멈추고 다음 원소로 넘어가기 때문
이미 정렬된 상태인 경우 O(N)의 시간 복잡도

function insertSort(arr) {
  for(let i=1; i<arr.length; i++) {
    // 인덱스 j부터 1까지 1씩 감소하며 반복
    for(let j=i; j>0; j--) {
      if(arr[j] < arr[j-1]) {
        // swap
        let temp = arr[j];
        arr[j] = arr[j-1];
        arr[j-1] = temp;
      } else {
        // 자기보다 작은 데이터를 만나면 그 위치에 멈춤
        break;
      }
    }
  }
}