알고리즘 쉘 정렬은 삽입 정렬의 단점을 보완하기 위해서 Donald Shell이 1958년 고안한 방법이다. 삽입 정렬은 Array 전체에 대해서 정렬을 수행하게 된다. 최악의 경우, 다시말해서 오름차순 정렬을 해야하는데, Array가 내림차순 정렬이 되어있는 경우 연산이 많아지게 될 수 밖에 없다. 쉘 정렬의 기본적인 아이디어는 삽입 정렬을 하기 전에 정리를 해놓자는 것이다. 그렇다면, 어떻게 정리할 것인가? 삽입 정렬은 모든 원소에 대해서 검사를 하지만, 쉘 정렬의 경우, 앞에서 구한 어떠한 간격만큼 떨어진 원소에 대해서 삽입정렬을 먼저 수행하고, 그 간격을 점점 줄여 계속 삽입정렬을 하는 방법을 취한다. 간격은 결국 1이 될 것이며, 1이 되는 때는 곧, 삽입 정렬을 수행하는 것과 동일하다. 하지만..