3단계 key에 4번 고양이를 배치하고 3번, 2번, 1번 고양이와 비교하는데, 비교하다가 key에 있는 고양이가 더 크면 더 이상 비교하지 않습니다.

1. key에 4번 고양이를 배치합니다.

 

2. key에 있는 고양이와 3번 고양이를 비교합니다.