Binaryworld - InsertionSort - A simple routine with minimal overhead ... [ VB -> Datastructure ]

' 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