InsertionSort - A simple routine with minimal overhead

' InsertionSort.  A simple routine with minimal overhead.  Should never be used 
' to sort long lists because of its O(N^2) behavior,
'  but is the method of choice for sorting short (5-50 key) lists or long lists 
' that have been mostly sorted by a faster algorithm.  InsertionSort is faster 
' than either Bubble or SelectionSort and should be used anywhere you would 
' consider using those.  Sorts in place (no extra memory needed) and is stable 
' (preserves the original order of records with equal keys).  Works by creating 
' a sorted list at the beginning of the array of keys.  As each unsorted key to 
' the right is examined, it is compared back thru the sorted list until the 
' right position to insert it is found.  Two versions are given.  pInsertS is 
' an indirect (pointerized) version for strings,
'  which can be adapted to doubles by changing the declaration of A().  InsertL 
' is a direct version for longs, which can be adapted to integers.
' 
' Speed:  Abysmally slow for anything but short lists.
'
' Bottom line:  should be used only to finish up for faster sorts with higher 
' overhead; for that purpose, this is the sort to choose.

' Usage:  

Dim S1(L To R) As String
Dim P1(L To R) As Long
Dim L1(L To R) As Long
 
For I = L To R
    S1(I) = GetRandomString()
    P1(I) = I
    L1(I) = GetRandomLong()
Next I

pInsertS L, R, S1, P1
InsertL L, R, L1

' CODE:

Sub pInsertS(L As Long, R As Long, A() As String, P() As Long)
    Dim LP As Long
    Dim RP As Long
    Dim TMP As Long
    Dim T As String

    'RP points to the first unsorted key.   
    For RP = L + 1 To R
     'Get the new value.
       TMP = P(RP)
        T = A(TMP)
    'Compare it back thru the sorted part as long as it's bigger.
        For LP = RP To L + 1 Step -1
            If T < A(P(LP - 1)) Then P(LP) = P(LP - 1) Else Exit For
        Next LP
    'It's bigger than all keys to the left, so insert it here.
        P(LP) = TMP
    Next RP
End Sub

Sub InsertL(L As Long, R As Long, A() As Long)
    Dim LP As Long
    Dim RP As Long
    Dim TMP As Long
    
    For RP = L + 1 To R
        TMP = A(RP)
        For LP = RP To L + 1 Step -1
            If TMP < A(LP - 1) Then A(LP) = A(LP - 1) Else Exit For
        Next LP
        A(LP) = TMP
    Next RP
End Sub