Shell Sort

Shell sort (a.k.a Shell's Method and Diminishing Increment Sort) is an in-place comparison sort algorithm. The method starts by sorting pairs of elements far apart from each other, then progressively reducing the gap between elements to be compared. Starting with far apart elements can move some out-of-place elements into position faster than a simple nearest neighbor exchange.

									void ShellSort(int* data, int count) {
	int hSort = 1;

	while (hSort < count / 3)
		hSort = (3 * hSort) + 1;

	while (hSort >= 1)
	{
		for (int i = hSort; i < count; i++)
		{
			for (int a = i; a >= hSort && (data[a] < data[a - hSort]); a -= hSort)
			{
				data[a] ^= data[a - hSort];
				data[a - hSort] ^= data[a];
				data[a] ^= data[a - hSort];
			}
		}

		hSort /= 3;
	}
}

Example

									int data[] = { -1, 25, -58964, 8547, -119, 0, 78596 };
ShellSort(data, 7);

Output