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.

									Public Shared Sub ShellSort(ByRef data As Integer())
	Dim hSort As Integer = 1

	While hSort < data.Length \ 3
		hSort = (3 * hSort) + 1
	End While

	While hSort >= 1
		For i As Integer = hSort To data.Length - 1
			Dim a As Integer = i
			While a >= hSort AndAlso (data(a) < data(a - hSort))
				data(a) = data(a) Xor data(a - hSort)
				data(a - hSort) = data(a - hSort) Xor data(a)
				data(a) = data(a) Xor data(a - hSort)
				a -= hSort
			End While
		Next

		hSort /= 3
	End While
End Sub

Example

									Dim data() As Integer = { -1, 25, -58964, 8547, -119, 0, 78596 }
ShellSort(data)

Output