Intro Sort

Intro sort (a.k.a Introspective Sort) is hybrid sorting algorithm that provides both fast average performance and optimal worst-case performance. It begins with Quick sort and switches to Heap sort when the recursion depth exceeds a level based on the number of elements being sorted.

									Public Shared Sub IntroSort(ByRef data As Integer())
	Dim partitionSize As Integer = Partition(data, 0, data.Length - 1)

	If partitionSize < 16 Then
		InsertionSort(data)
	ElseIf partitionSize > (2 * Math.Log(data.Length)) Then
		HeapSort(data)
	Else
		QuickSortRecursive(data, 0, data.Length - 1)
	End If
End Sub

Private Shared Sub InsertionSort(ByRef data As Integer())
	For i As Integer = 1 To data.Length - 1
		Dim j As Integer = i

		While (j > 0)
			If data(j - 1) > data(j) Then
				data(j - 1) = data(j - 1) Xor data(j)
				data(j) = data(j) Xor data(j - 1)
				data(j - 1) = data(j - 1) Xor data(j)

				j -= 1
			Else
				Exit While
			End If
		End While
	Next
End Sub

Private Shared Sub HeapSort(ByRef data As Integer())
	Dim heapSize As Integer = data.Length

	For p As Integer = (heapSize - 1) \ 2 To 0 Step -1
		MaxHeapify(data, heapSize, p)
	Next

	For i As Integer = data.Length - 1 To 1 Step -1
		Dim temp As Integer = data(i)
		data(i) = data(0)
		data(0) = temp

		heapSize -= 1
		MaxHeapify(data, heapSize, 0)
	Next
End Sub

Private Shared Sub MaxHeapify(ByRef data As Integer(), heapSize As Integer, index As Integer)
	Dim left As Integer = (index + 1) * 2 - 1
	Dim right As Integer = (index + 1) * 2
	Dim largest As Integer = 0

	If left < heapSize AndAlso data(left) > data(index) Then
		largest = left
	Else
		largest = index
	End If

	If right < heapSize AndAlso data(right) > data(largest) Then
		largest = right
	End If

	If largest <> index Then
		Dim temp As Integer = data(index)
		data(index) = data(largest)
		data(largest) = temp

		MaxHeapify(data, heapSize, largest)
	End If
End Sub

Private Shared Sub QuickSortRecursive(ByRef data As Integer(), left As Integer, right As Integer)
	If left < right Then
		Dim q As Integer = Partition(data, left, right)
		QuickSortRecursive(data, left, q - 1)
		QuickSortRecursive(data, q + 1, right)
	End If
End Sub

Private Shared Function Partition(ByRef data As Integer(), left As Integer, right As Integer) As Integer
	Dim pivot As Integer = data(right)
	Dim temp As Integer
	Dim i As Integer = left

	For j As Integer = left To right - 1
		If data(j) <= pivot Then
			temp = data(j)
			data(j) = data(i)
			data(i) = temp
			i += 1
		End If
	Next

	data(right) = data(i)
	data(i) = pivot

	Return i
End Function

Example

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

Output