셸 정렬

삽입 정렬을 바로 옆 원소가 아니라 일정 간격(gap)만큼 떨어진 원소끼리 먼저 하고, 간격을 점점 줄여 마지막에 간격 1(보통의 삽입 정렬)로 마무리하는 정렬이다. 멀리 떨어진 값을 한 번에 크게 옮겨 두기 때문에 마지막 삽입 정렬이 거의 정렬된 데이터를 받게 된다. 성능은 간격을 줄이는 방식에 따라 달라진다.