Insertion Sort

How this works is it takes the existing sorted ones and inserts between where it would fit. So 1, 3 <- 2 would have 2 inserted like 1, 2, 3. The nice thing is it does this in one pass, but during that pass it has to keep looping back. Making this O(n^2).

Notice where we make a copy by value 1 for use later. Also 2 notice how we keep track where to insert it.

func (arr *Array[T]) InsertionSort() {
  var extractedV T
  var p2 int
  for j := 1; j < len(*arr); j++ {
    extractedV = (*arr)[j]
    p2 = j
    for i := j; i > 0; i-- {
      if Less(extractedV, (*arr)[i-1]) {
        (*arr)[i] = (*arr)[i-1]
        p2--
      }
    }
    (*arr)[p2] = extractedV
  }
}