Insertion sort implementation in scala

Question

I'm trying out Scala and I want to see how one would implement insertion sort in scala with the following requirements:

1. Nested for loops
2. Array[Int] for input
3. If possible a way to modify the contents of the function in a call by reference way otherwise return an Array[Int]

If this isn't the Scala way of implementing insertion sort can you still provide code for the above and explain what is wrong with the approach. edit: This is an attempt using a while loop (doest work) and no it isn't a homework question, why the hostility?

def insert_sort(a:Array[Int]):Array[Int]={
for(i <- 0 until a.length)
{
  var j=i+1

  while(j>1&&a(j)<a(j-1)&&j<a.length)
  {
      var c=a(j)
      a(j)=a(j-1)
      a(j-1)=c
      j-=1
  }
}
return a
}

Answer 1

This is what I came up with, which seems to be functional, generic, tail-recursive (foldLeft is tail-recursive)...:

def insertionSort[A](la: List[A])(implicit ord: Ordering[A]): List[A] = {
  def insert(la: List[A], a: A) = {
    val (h, t) = la.span(ord.lt(_, a))
    h ::: (a :: t)
  }

  la.foldLeft(List[A]()) {(acc, a) => insert(acc, a)}
}

Answer 2

The most elegant insertion sort algorithm implementation that I'we seen so far:

val rand = List(5,3,1,2)

def isort(xs: List[Int]): List[Int] =
  if (xs.isEmpty) Nil
  else insert(xs.head, isort(xs.tail))

def insert(x: Int, xs: List[Int]): List[Int] =
  if (xs.isEmpty || x <= xs.head) x :: xs
  else xs.head :: insert(x, xs.tail)

isort(rand) // Produces List(1,2,3,5)

Algorithm implementation is taken from this great book: https://www.artima.com/shop/programming_in_scala_3ed