Merge Sort Recursive

Merge sort is a Divide and Conquer algorithm. It divides input array in two halves, calls itself for the two halves and then merges the two sorted halves.

									Public Shared Sub MergeSortRecursive(ByRef data As Integer(), left As Integer, right As Integer)
	If left < right Then
		Dim m As Integer = left + (right - left) \ 2

		MergeSortRecursive(data, left, m)
		MergeSortRecursive(data, m + 1, right)
		Merge(data, left, m, right)
	End If
End Sub

Private Shared Sub Merge(ByRef data As Integer(), left As Integer, mid As Integer, right As Integer)
	Dim i As Integer, j As Integer, k As Integer
	Dim n1 As Integer = mid - left + 1
	Dim n2 As Integer = right - mid
	Dim L As Integer() = New Integer(n1 - 1) {}
	Dim R As Integer() = New Integer(n2 - 1) {}

	For i = 0 To n1 - 1
		L(i) = data(left + i)
	Next

	For j = 0 To n2 - 1
		R(j) = data(mid + 1 + j)
	Next

	i = 0
	j = 0
	k = left

	While i < n1 AndAlso j < n2
		If L(i) <= R(j) Then
			data(k) = L(i)
			i += 1
		Else
			data(k) = R(j)
			j += 1
		End If

		k += 1
	End While

	While i < n1
		data(k) = L(i)
		i += 1
		k += 1
	End While

	While j < n2
		data(k) = R(j)
		j += 1
		k += 1
	End While
End Sub

Example

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

Output