알고리즘 - 셸 정렬

- shell sort

- 삽입 정렬이 어느 정도 정렬된 배열에 대해서는 대단히 빠른 것을 착안한 방법

- 셸 정렬은 삽입 정렬의 보다 빠르다.

- 전체의 리스트를 한 번에 정렬하지 않고, 먼저 정렬해야 할 리스트를 일정한 기준에 따라 분류하여 연속적이지 않은 여러 개의 부분 리스트를 만들고, 각 부분 리스트를 삽입 정렬을 이용하여 정렬

- gap만큼 떨어진 요소들을 삽입 정렬하고, gap을 반씩 줄여가면서 1까지 반복

- 최악의 경우의 시간복잡도 지만 평균적인 경우는 로 삽입 정렬보다 빠르다

출처: http://wonjayk.tistory.com/220