[Squirm]

Comb Sort
The main problem with the bubblesort is something called the rabbit-turtle effect. Large values at the bottom bubble up very quickly (rabbits) but small values at the top take many many passes to sink (turtles). The comb sort overcomes this by comparing non-adjacent values. This means turtles have the chance to jump down the list much quicker. We repeat the process with smaller and smaller spacings until we finish with a simple bubblesort.

Example:

Array of data [6,7,9,3,2,5]

[6,7,9,3,2,5]
         ^ Potential turtle

Combing pass with a spacing of 4
[6,7,9,3,2,5]
[2,7,9,3,6,5]

Combing pass with a spacing of 3
[2,5,9,3,6,7]
[2,5,9,3,6,7]
[2,5,9,3,6,7]

Combing pass with a spacing of 2
[2,5,7,3,6,9]
[2,5,7,3,6,9]
[2,3,7,5,6,9]
[2,3,6,5,7,9]

Combing pass with a spacing of 1
[2,3,6,5,7,9]
[2,3,6,5,7,9]
[2,3,6,5,7,9]
[2,3,5,6,7,9]
[2,3,5,6,7,9]

Finish [2,3,5,6,7,9]

If you trawl the web for a bit you'll find this sort, like every other, has been well studied. It has been found that if the spacing ever reaches 11, the remaining few passes are much more efficient than if 9 or 10 are used. The result is often called the Comb11 Sort:

Public Sub CombSort(ByRef lngArray() As Long)
    Dim iSpacing As Long
    Dim iOuter As Long
    Dim iInner As Long
    Dim iTemp As Long
    Dim iLBound As Long
    Dim iUBound As Long
    Dim iArrSize As Long
    Dim iFinished As Long
    
    iLBound = LBound(lngArray)
    iUBound = UBound(lngArray)
    
    'Initialise comb width
    iSpacing = iUBound - iLBound
    
    Do
        If iSpacing > 1 Then
            iSpacing = Int(iSpacing / 1.3)
            
            If iSpacing = 0 Then
                iSpacing = 1  'Dont go lower than 1
            ElseIf iSpacing > 8 And iSpacing < 11 Then
                iSpacing = 11 'This is a special number, goes faster than 9 and 10
            End If
        End If
        
        'Always go down to 1 before attempting to exit
        If iSpacing = 1 Then iFinished = 1
        
        'Combing pass
        For iOuter = iLBound To iUBound - iSpacing
            iInner = iOuter + iSpacing
            
            If lngArray(iOuter) > lngArray(iInner) Then
                'Swap
                iTemp = lngArray(iOuter)
                lngArray(iOuter) = lngArray(iInner)
                lngArray(iInner) = iTemp
                
                'Not finished
                iFinished = 0
            End If
        Next iOuter
        
    Loop Until iFinished
End Sub