• 이미 정렬된 부분 영역에서 데이터를 하나씩 확인하여 적절한 위치에 삽입하는 방식
• 부분적으로 정렬되었다면 효율적이겠지만, 데이터가 클수록 성능이 저하된다
• 시간 복잡도 : O(n^2), 공간 복잡도 : O(1)

fun insertionSort(arr: IntArray) {
    val n = arr.size
    for (i in 1 until n) {
        // 정렬할 Key, 새로운 카드
        val key = arr[i]
        var j = i - 1
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j]
            j--
        }
        arr[j + 1] = key
    }
}