OpenNTF Code Bin
About This Code
Brief Description:
In Place Merge Sort
Contributor:
Michael Fariborz
Notes Version:
R4.x, R6.x, R8.x, R5.x, R7.x
Last Modified:
01 Apr 2008
OpenNTF Disclaimer
All of the program code and information presented in the OpenNTF.org Code Bin are provided "as-is", and should be used at your own risk. OpenNTF.org make no express or implied warranty about anything in the Code Bin, and OpenNTF.org will not be responsible or liable for any damage caused by the use or misuse of anything from this site. OpenNTF.org makes no guarantees about anything. Please thoroughly test all of the knowledge and code you find here before you attempt to use them in your production environment.
Code / Description
According to Wikipedia InPlaceMergeSort is a pretty fast sorting algorithm (O(n log n) on average, O(n log n) worst case and O(1) memory usage.)
Sub InPlaceMergeSort(vArray As Variant, nLow0 As Integer, nHigh0 As Integer)
Dim nLow As Integer
Dim nHigh As Integer
Dim nMid As Integer
Dim nEndLow As Integer
Dim nStartHigh As Integer
Dim vTemp As Variant
Dim nCount As Integer
nLow = nLow0
nHigh = nHigh0
If nLow >= nHigh Then
Exit Sub
End If
nMid = (nLow + nHigh) \ 2
Call InPlaceMergeSort(vArray, nLow, nMid)
Call InPlaceMergeSort(vArray, nMid + 1, nHigh)
nEndLow = nMid
nStartHigh = nMid + 1
While nLow <= nEndLow And nStartHigh <= nHigh
If vArray(nLow) < vArray(nStartHigh) Then
nLow = nLow + 1
Else
vTemp = vArray(nStartHigh)
For nCount = nStartHigh -1 To nLow Step -1
vArray(nCount + 1) = vArray(nCount)
Next
vArray(nLow) = vTemp
nLow = nLow + 1
nEndLow = nEndLow + 1
nStartHigh = nStartHigh + 1
End If
Wend
End Sub
Sub sort(vArray As Variant)
Call InPlaceMergeSort(vArray, Lbound(vArray), Ubound(vArray))
End Sub
Usage / Example
Dim vArray(0 To 1) As String
vArray(0) = "World"
vArray(1) = "Hello"
Call sort(vArray)
'After the sort call, the array will have Hello as it's first entry and World as it's second.
Comments
Posted by Dietrich Willing on 07/30/2008 08:27:30 AMInPlaceMergeSort for two dimensional arrays
I love what you've written.
When you have a collection of documents and you want to sort them by a field value (string number or date), create a two dimensional array with the value to be sorted in the first dimension and the unid in the second.
A few changes to the code are needed:
Sub InPlaceMergeSortMulti(vArray As Variant, nLow0 As Integer, nHigh0 As Integer)
Dim nLow As Integer
Dim nHigh As Integer
Dim nMid As Integer
Dim nEndLow As Integer
Dim nStartHigh As Integer
Dim vTemp As Variant
Dim vTemp1 As Variant ' holds the second dimensional value
Dim nCount As Integer
nLow = nLow0
nHigh = nHigh0
If nLow >= nHigh Then
Exit Sub
End If
nMid = (nLow + nHigh) \ 2
Call InPlaceMergeSortMulti(vArray, nLow, nMid)
Call InPlaceMergeSortMulti(vArray, nMid + 1, nHigh)
nEndLow = nMid
nStartHigh = nMid + 1
While nLow <= nEndLow And nStartHigh <= nHigh
If vArray(nLow, 0) < vArray(nStartHigh, 0) Then 'compare the first dimensional values
nLow = nLow + 1
Else
vTemp = vArray(nStartHigh, 0)
vTemp1 = vArray(nStartHigh, 1)
For nCount = nStartHigh -1 To nLow Step -1
vArray(nCount + 1, 0) = vArray(nCount, 0)
vArray(nCount + 1, 1) = vArray(nCount, 1)
Next
vArray(nLow, 0) = vTemp
vArray(nLow, 1) = vTemp1
nLow = nLow + 1
nEndLow = nEndLow + 1
nStartHigh = nStartHigh + 1
End If
Wend
End Sub
Sub sortMulti(vArray As Variant)
Call InPlaceMergeSortMulti(vArray, Lbound(vArray), Ubound(vArray))
End Sub
Usage:
Dim vArray(0 To 2, 0 To 1) As String
vArray(0,0) = "World"
vArray(0, 1) = "0057EF6A0D14DA33CA25733600029AA6"
vArray(1, 0) = "Hello"
vArray(1, 1) = "31687E1C78B7F928CA257339000FE92F"
vArray(2, 0) = "this"
vArray(2, 1) = "65AEE9355C1F5270CA257331000C0B83"
Call sortMulti(vArray)
and for dates:
Dim vArray(0 To 2, 0 To 1) As Variant
vArray(0, 0) = Today
vArray(0, 1) = "0057EF6A0D14DA33CA25733600029AA6"
vArray(1, 0) = Datenumber(2008, 7, 26)
vArray(1, 1) = "31687E1C78B7F928CA257339000FE92F"
vArray(2, 0) = Datenumber(2008, 7, 16)
vArray(2, 1) = "65AEE9355C1F5270CA257331000C0B83"
Call sortMulti(vArray)