Sorting data using VBA: Merge Sort
2020-06-14 Sorting 0 267
MergeSort: Sorting large two-dimensional arrays:
MergeSort is suitable for sorting two-dimensional arrays very fast, it is almost as fast as the built-in sort in Excel.
MergeSort is a stable sort method, items with equal sort keys are returned in the same order in the sorted result as they had before being sorted.
MergeSort can also be used to sort two-dimensional arrays that has a header row.
NOTE: The sorting algorithm in this document is adapted for use in VBA based on detailed descriptions found in Wikipedia.
Sub MergeSort(varArray As Variant, Optional lngSortColumn As Long = -1, Optional blnCompareText As Boolean = False, _
Optional blnHasHeaderRow As Boolean = False, Optional lngSortOrder As XlSortOrder = xlAscending)
' updated 2019-05-16 by OPE
' sorts a two-dimensional array in ascending or descending order based on the content in column lngSortColumn
' lngSortColumn must be an integer number >= LBound(varArray, 2) and <= UBound(varArray, 2), uses LBound(varArray, 2) if lngSortColumn < 0
' fast and stable sort method, items with equal sort keys are returned in the same order in the sorted result as they had before being sorted
' example: MergeSort varArrayVariable, 1
Dim i As Long, j As Long, varArray1 As Variant, varArray2 As Variant
Dim blnTwoItemsOnly As Boolean, blnSwap As Boolean, c As Long, varTemp As Variant, varCaption As Variant
If MergeSort_DimCount(varArray, i, j) <> 2 Then Exit Sub
If blnHasHeaderRow Then
If i <= 2 Then Exit Sub ' nothing to sort
Else
If i <= 1 Then Exit Sub ' nothing to sort
End If
If j < 1 Then Exit Sub ' nothing to sort
If lngSortColumn < 0 Then lngSortColumn = LBound(varArray, 2)
If lngSortColumn < LBound(varArray, 2) Or lngSortColumn > UBound(varArray, 2) Then Exit Sub
blnTwoItemsOnly = False
If blnHasHeaderRow And i = 3 Then
blnTwoItemsOnly = True
i = LBound(varArray, 1) + 1
End If
If Not blnHasHeaderRow And i = 2 Then
blnTwoItemsOnly = True
i = LBound(varArray, 1)
End If
If blnTwoItemsOnly Then
blnSwap = False
If lngSortOrder = xlAscending Then ' xlAscending=1, xlDescending=2
If blnCompareText Then
blnSwap = StrComp(varArray(i, lngSortColumn), varArray(i + 1, lngSortColumn), vbTextCompare) > 0
Else
blnSwap = varArray(i, lngSortColumn) > varArray(i + 1, lngSortColumn)
End If
Else
If blnCompareText Then
blnSwap = StrComp(varArray(i, lngSortColumn), varArray(i + 1, lngSortColumn), vbTextCompare) < 0
Else
blnSwap = varArray(i, lngSortColumn) < varArray(i + 1, lngSortColumn)
End If
End If
If blnSwap Then
For c = LBound(varArray, 2) To UBound(varArray, 2)
varTemp = varArray(i, c)
varArray(i, c) = varArray(i + 1, c)
varArray(i + 1, c) = varTemp
Next c
End If
Exit Sub
End If
If blnHasHeaderRow Then
i = LBound(varArray, 1)
varCaption = varArray(i, lngSortColumn) ' save original column header
If blnCompareText Then
If lngSortOrder = xlAscending Then ' xlAscending=1, xlDescending=2
varArray(i, lngSortColumn) = Empty
Else
varArray(i, lngSortColumn) = Replace(Space(30), " ", "å") ' this might be a different character depending on the regional settings
End If
Else
If lngSortOrder = xlAscending Then ' xlAscending=1, xlDescending=2
varArray(i, lngSortColumn) = -1E+300 ' very large negative number
Else
varArray(i, lngSortColumn) = 1E+300 ' very large positive number
End If
End If
End If
MergeSort_Split varArray, varArray1, varArray2
If IsArray(varArray1) Then
MergeSort varArray1, lngSortColumn, blnCompareText, blnHasHeaderRow, lngSortOrder
End If
If IsArray(varArray2) Then
MergeSort varArray2, lngSortColumn, blnCompareText, False, lngSortOrder
End If
varArray = MergeSort_Merge(varArray1, varArray2, lngSortColumn, blnCompareText, lngSortOrder)
If blnHasHeaderRow Then
i = LBound(varArray, 1)
varArray(i, lngSortColumn) = varCaption ' restore original column header
End If
End Sub
Private Sub MergeSort_Split(varArray As Variant, Optional varArray1 As Variant, Optional varArray2 As Variant)
' updated 2019-05-16 by OPE
' splits a two-dimensional array into two two-dimensional arrays: varArray1 and varArray2
Dim i As Long, lngCount As Long, m As Long, v() As Variant, r As Long, c As Long
varArray1 = False: varArray2 = False
i = MergeSort_DimCount(varArray, lngCount) ' dimension count and items count
If i <> 2 Then Exit Sub ' not a two-dimensional array
If lngCount < 1 Then Exit Sub ' no content in array
If lngCount = 1 Then ' nothing to split
varArray1 = varArray
Exit Sub
End If
m = Int(lngCount / 2)
If lngCount Mod 2 <> 0 Then m = m + 1
ReDim v(LBound(varArray, 1) To LBound(varArray, 1) + m - 1, LBound(varArray, 2) To UBound(varArray, 2))
i = LBound(varArray, 1) - 1
' add items
For r = LBound(varArray, 1) To LBound(varArray, 1) + m - 1
i = i + 1
For c = LBound(varArray, 2) To UBound(varArray, 2)
v(i, c) = varArray(r, c)
Next c
Next r
varArray1 = v
If lngCount Mod 2 = 0 Then
ReDim v(LBound(varArray, 1) To LBound(varArray, 1) + m - 1, LBound(varArray, 2) To UBound(varArray, 2))
Else
ReDim v(LBound(varArray, 1) To LBound(varArray, 1) + m - 2, LBound(varArray, 2) To UBound(varArray, 2))
End If
i = LBound(varArray, 1) - 1
' add items
For r = LBound(varArray, 1) + m To UBound(varArray, 1)
i = i + 1
For c = LBound(varArray, 2) To UBound(varArray, 2)
v(i, c) = varArray(r, c)
Next c
Next r
varArray2 = v
End Sub
Private Function MergeSort_Merge(varArray1 As Variant, varArray2 As Variant, Optional lngSortColumn As Long = -1, _
Optional blnCompareText As Boolean = False, Optional lngSortOrder As XlSortOrder = xlAscending) As Variant
' updated 2019-05-16 by OPE
' merges two two-dimensional arrays into one in ascending or descending order
Dim lngRows(0 To 2) As Long, lngCols As Long, r As Long, c As Long, i As Long, j As Long
Dim varArray() As Variant, i1 As Long, i2 As Long
MergeSort_Merge = False
i = MergeSort_DimCount(varArray1, lngRows(1)) ' dimension count and items count
j = MergeSort_DimCount(varArray2, lngRows(2)) ' dimension count and items count
If i <> 2 And j <> 2 Then Exit Function ' not two two-dimensional arrays
If lngRows(1) < 1 Then ' no content i array1
If lngRows(2) > 0 Then ' has content i array2
MergeSort_Merge = varArray2
End If
Exit Function
End If
If lngRows(2) < 1 Then ' no content i array2
If lngRows(1) > 0 Then ' has content i array1
MergeSort_Merge = varArray1
End If
Exit Function
End If
If lngSortColumn < 0 Then lngSortColumn = LBound(varArray1, 2)
If lngSortColumn < LBound(varArray1, 2) Or lngSortColumn > UBound(varArray1, 2) Then Exit Function
If lngSortColumn < LBound(varArray2, 2) Or lngSortColumn > UBound(varArray2, 2) Then Exit Function
lngRows(0) = lngRows(1) + lngRows(2) ' total row count
lngCols = UBound(varArray1, 2) - LBound(varArray1, 2) + 1
c = UBound(varArray2, 2) - LBound(varArray2, 2) + 1
If c > lngCols Then lngCols = c
ReDim varArray(LBound(varArray1, 1) To lngRows(0) + LBound(varArray1, 1) - 1, LBound(varArray1, 2) To lngCols + LBound(varArray1, 2) - 1) ' result array
r = LBound(varArray1, 1) - 1
i1 = LBound(varArray1, 1)
i2 = LBound(varArray2, 1)
Do While i1 <= UBound(varArray1, 1) And i2 <= UBound(varArray2, 1)
r = r + 1
c = LBound(varArray, 2) - 1
If lngSortOrder = xlAscending Then ' xlAscending=1, xlDescending=2
If blnCompareText Then
If StrComp(varArray1(i1, lngSortColumn), varArray2(i2, lngSortColumn), vbTextCompare) <= 0 Then
For j = LBound(varArray1, 2) To UBound(varArray1, 2)
c = c + 1
varArray(r, c) = varArray1(i1, j)
Next j
i1 = i1 + 1
Else
For j = LBound(varArray2, 2) To UBound(varArray2, 2)
c = c + 1
varArray(r, c) = varArray2(i2, j)
Next j
i2 = i2 + 1
End If
Else
If varArray1(i1, lngSortColumn) <= varArray2(i2, lngSortColumn) Then
For j = LBound(varArray1, 2) To UBound(varArray1, 2)
c = c + 1
varArray(r, c) = varArray1(i1, j)
Next j
i1 = i1 + 1
Else
For j = LBound(varArray2, 2) To UBound(varArray2, 2)
c = c + 1
varArray(r, c) = varArray2(i2, j)
Next j
i2 = i2 + 1
End If
End If
Else
If blnCompareText Then
If StrComp(varArray1(i1, lngSortColumn), varArray2(i2, lngSortColumn), vbTextCompare) >= 0 Then
For j = LBound(varArray1, 2) To UBound(varArray1, 2)
c = c + 1
varArray(r, c) = varArray1(i1, j)
Next j
i1 = i1 + 1
Else
For j = LBound(varArray2, 2) To UBound(varArray2, 2)
c = c + 1
varArray(r, c) = varArray2(i2, j)
Next j
i2 = i2 + 1
End If
Else
If varArray1(i1, lngSortColumn) >= varArray2(i2, lngSortColumn) Then
For j = LBound(varArray1, 2) To UBound(varArray1, 2)
c = c + 1
varArray(r, c) = varArray1(i1, j)
Next j
i1 = i1 + 1
Else
For j = LBound(varArray2, 2) To UBound(varArray2, 2)
c = c + 1
varArray(r, c) = varArray2(i2, j)
Next j
i2 = i2 + 1
End If
End If
End If
Loop
Do While i1 <= UBound(varArray1, 1)
r = r + 1
c = LBound(varArray, 2) - 1
For j = LBound(varArray1, 2) To UBound(varArray1, 2)
c = c + 1
varArray(r, c) = varArray1(i1, j)
Next j
i1 = i1 + 1
Loop
Do While i2 <= UBound(varArray2, 1)
r = r + 1
c = LBound(varArray, 2) - 1
For j = LBound(varArray2, 2) To UBound(varArray2, 2)
c = c + 1
varArray(r, c) = varArray2(i2, j)
Next j
i2 = i2 + 1
Loop
MergeSort_Merge = varArray
End Function
Private Function MergeSort_DimCount(varArray As Variant, Optional lngRows As Long = 0, Optional lngCols As Long = 0, Optional lngZ As Long = 0) As Long
' updated 2019-05-16 by OPE
' returns the count of array dimensions in varArray
' returns -1 if varArray is not an array variable
' returns 0 if varArray is an undimensioned array variable
' lngRows: returns the count of items in the first array dimension
' lngCols: returns the count of items in the second array dimension
' lngZ: returns the count of items in the third array dimension
Dim blnIsArray As Boolean, d As Long
MergeSort_DimCount = -1: lngRows = 0: lngCols = 0: lngZ = 0
If Not IsArray(varArray) Then Exit Function ' not an array variable
d = 0
Err.Clear
On Error Resume Next ' ignore error for unallocated array dimensions
Do While IsNumeric(UBound(varArray, d + 1))
If Err.Number = 0 Then
d = d + 1
Else
Exit Do
End If
Loop
If d > 0 Then
lngRows = UBound(varArray, 1) - LBound(varArray, 1) + 1
lngCols = UBound(varArray, 2) - LBound(varArray, 2) + 1
lngZ = UBound(varArray, 3) - LBound(varArray, 3) + 1
End If
On Error GoTo 0
MergeSort_DimCount = d
End Function
Here are some of the options you can use to sort data in Excel using VBA:
Stable sort methods:
RangeSort, TableSort, BubbleSort, MergeSort and the SORT worksheet function are stable sort methods:
Items with equal sort keys are returned in the same order in the sorted result as they had before being sorted.
QuickSort and ShellSort are not stable sort methods and you would normally not want to use these with two-dimensional arrays.
See this post if you need information about how to read from and write to worksheet cells using array variables.