# Visual Basic 2010 (Console) GuideInsertion Sort

The insertion sort is the closest sort algorithm to the way that we might sort the array if we wrote the numbers on some cards. Imagine that this is the case. You would take the first card and place it on the table. You would then take the second card and place it to the left or right of the first one depending on whether it was greater or less than that item. When the third card is taken, if it goes at the start of the list, you would need to shuffle the other cards to the right to put it in the correct position.

The following algorithm can be used for an insertion sort,

For outerLoop = 1 To arrayLength - 1
temp = item[outerLoop]
innerLoop = outerLoop
While (innerLoop > 0 And item[innerLoop - 1] >= temp)
item[innerLoop] = item[innerLoop - 1]
innerLoop = innerLoop - 1
End While
item[innerLoop] = temp
Next outerLoop

## Insertion Sort Example

The following sample generates a random array of 10000 doubles. We are not concerned with looking at these values here, just the time it takes to execute the sort. The stopwatch is used here to time the execution.

Dim randomArray(10000) As Double

Sub RandomNumbers()
Dim rand As New Random()
For count = 0 To randomArray.Length - 1
randomArray(count) = rand.NextDouble()
Next
End Sub

Sub InsertionSort()
Dim temp As Double
Dim inner As Integer, outer As Integer
For outer = 0 To randomArray.Length - 1
temp = randomArray(outer)
inner = outer
While inner > 0 AndAlso randomArray(inner - 1) >= temp
randomArray(inner) = randomArray(inner - 1)
inner -= 1
End While
randomArray(inner) = temp
Next
End Sub

Sub Main()
Randomize()
RandomNumbers()
Dim stopWatch As New Stopwatch()
stopWatch.Reset()
stopWatch.Start()
InsertionSort()
stopWatch.Stop()
Console.WriteLine("Insertion Sort Took {0} Milliseconds", stopWatch.ElapsedMilliseconds)