import Ordering.Implicits._

def insertionSort[T:Ordering](a: Array[T]) : Unit = {
  for( i <- 1 until a.length) insert(a, i-1, a(i))
}

def insert[T:Ordering](a: Array[T], rightIndex: Int, x: T) {
  var i = rightIndex
  while (i >= 0 && a(i) > x)  {
      a(i+1) = a(i)
      i -= 1
  }

  a(i + 1) = x

}