작동 원리 : Insertion Sort 의 발전된 형태. 바로 전 원소와 비교하는 것이 아니라 h만큼 떨어진 원소와 비교한다. 일반적으로 h = 3 * h + 1 수열을 많이 사용한다.

시간복잡도 : O(n^1.5)

• Required Function : swap

void swap(int *dest, int *src)
{
	int tmp;

	tmp = *dest;
	*dest = *src;
	*src = tmp;
}

C++, C

void shell_sort(int *arr, int length)
{
	int h = 1;
	while(h < length / 3)
		h = 3 * h + 1;
	while(h >= 1)
	{
		for (int i = h; i <length ; i++)
			for (int j = i; j >= h && arr[j] < arr[j - h] ; j -= h)
				swap((arr + j), (arr + j - h ));
		h /= 3;
	}
}