쉘정렬 알고리즘 시간 복잡도

// gap 만큼 떨어진 요소들을 삽입 정렬
// 정렬의 범위는 first에서 last
inc_insertion_sort(int list[], int first, int last, int gap)
{
    int i, j, key;
    for(i=first+gap; i<=last; i=i+gap){
        key = list[i];
        for(j=i-gap; j>=first && key<list[j];j=j-gap)
            list[j+gap]=list[j];
        list[j+gap]=key;
    }
}
//
void shell_sort( int list[], int n )   // n = size
{
    int i, gap;
    for( gap=n/2; gap>0; gap = gap/2 ) {
        if( (gap%2) == 0 ) gap++;
        for(i=0;i<gap;i++)        // 부분 리스트의 개수는 gap
            inc_insertion_sort(list, i, n-1, gap);
    }
}

삽입정렬이 어느 정도 정렬된 배열에 대해서는 대단히 빠른 것에 착안한 방법
셀정렬은 삽입 정렬보다 빠르다. 
삽입 정렬의 최대 문제점은 요소들이 이동할 때, 이웃한 위치로만 이동
쉘정렬에서는 요소들이 멀리 떨어진 위치로도 이동할 수 있다.  
전체 리스트를 일정 간격의 부분 리스트로 나누고 부분 리스트를 정렬한다.
간격(gap)은 점점 줄어들게 된다.
평균적인 경우 시간복잡도는 O(n1.5)