One API that seems to be missing from List(Of T) is a BinaryInsert method. Especially since there is already a BinarySearch method.
Binary insert is a method for inserting a value into an already sorted list. Since the list is already sorted we can do a binary search to find the appropriate place to insert. The insert keeps the list sorted so the cost of a binary insert is just the cost of the search which is O(Log(N)).
An alternative method for keeping a sorted list sorted is to insert and then resort. Most sorting algorithms have a cost of O(N*Log(N)). In other words it's N times more expensive.
Yet this API doesn't exist. No matter. We can quickly fix this problem with a couple of extension methods.
Public Module Extensions
Public Sub BinaryInsert(Of T)(ByVal list As List(Of T), ByVal value As T, ByVal comp As IComparer(Of T))
list.BinaryInsert(value, comp, 0, list.Count)
Public Sub BinaryInsert(Of T)(ByVal list As List(Of T), _
ByVal value As T, _
ByVal comparer As IComparer(Of T), _
ByVal iStart As Integer, _
ByVal iEnd As Integer)
While iStart < iEnd
Dim len = iEnd - iStart
Dim iMiddle = iStart + (len \ 2)
Dim comp = comparer.Compare(value, list(iMiddle))
If 0 = comp Then
iStart = iMiddle
ElseIf comp < 0 Then
iEnd = iMiddle
iStart = iMiddle + (len Mod 2)