VBA sorting: InsertionSort

If your data to be sorted is always nearly sorted already then you probably should be using InsertionSort. In that particular use case this sorting algorithm is considerably faster than practically all other sorting algorithms, including QuickSort.

However, if your data is not always nearly sorted, or you don’t know if it is, then you probably shouldn’t be using this algorithm as it’s much slower than e.g. QuickSort in practically all other use cases. Just like QuickSort, this algorithm sorts the data in-place, i.e. without using any auxiliary data structures and the input array must be one-dimensional.

Function

VBA
Sub InsertionSort(arr As Variant)

    Dim i As Long, j As Long
    Dim temp As Variant
    
    For i = LBound(arr) + 1 To UBound(arr)
        j = i
        Do While j > 0
            If arr(j - 1) > arr(j) Then
                temp = arr(j)
                arr(j) = arr(j - 1)
                arr(j - 1) = temp
            Else
                Exit Do
            End If
            j = j - 1
        Loop
    Next i

End Sub

Parameters

Usage example

VBA
Sub TestInsertionSort()

    Dim i As Long
    Dim arr(0 To 9) As Variant

    For i = 0 To 9
        If i = 7 Then arr(i) = i - 1 Else arr(i) = i + 1
        Debug.Print i & ": " & arr(i)
    Next i
    ' result: 1,2,3,4,5,6,7,6,9,10
    
    Call InsertionSort(arr)
    For i = 0 To 9
        Debug.Print i & ": " & arr(i)
    Next i
    ' result: 1,2,3,4,5,6,6,7,9,10
    
End Sub