Insertion sort implementation in scala

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)}
}

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

My version of the insertion sort procedure is the following. It consists of two functions, isort and insert which have the following signatures:

• isort(xs: List[int]) : List[int]: Takes an input list of integers and outputs a list of integers.
• insert(x: Int, xs: List[int]) : List[int] Takes a sorted input list and an integer x and adds x to the right position in the list to maintain the invariant that the list is sorted. Example: insert(3, [1, 2]) = [1, 2, 3]

First let us code up the insert function.

1. If the list is empty, return a list of the integer to be added.

2. Otherwise, there are two possible cases. The head of the list is greater or equal to the given input integer, in which case we simply append the input integer to the beginning of the list and return it. The other case is when the input integer is greater than the head of the input list. In this case, we recursively insert the input integer into the tail of the list.

   def insert(x : Int, xs : List[Int]) : List[Int] = {
   
   xs match{
       case Nil => List(x)
       case y :: xs1 =>
           if(y >= x) x :: xs
           else y :: insert(x,  xs1)
    }
   
   }
   

The second function is isort, which takes an input list and sorts it. The algorithm is as follows:

1. If the input list is equal to Nil, return Nil.

2. Otherwise, recursively sort the tail of the list, and add the head at the right position in the (sorted) tail (using the insert procedure)

    def isort(xs : List[Int]) : List[Int] = {
     xs match{
       case Nil => Nil
       case x :: xs1 => insert(x, isort(xs1))
   
      }
   
    } 
   

We can test this as isort(List(1, 6, 4, -2, 5, 12)) and we get the correct expected output.

Nested for loops are probably not the answer in Scala, whatever is the problem. They make sense in languages where for loops stand for "repeat until condition, changing this each iteration", which is not what for loops or for comprehensions are in Scala (a for comprehension is a for loop which yields something for each iteration).

In Scala, for loops and for comprehensions are iterations over the elements of a collection (or weirder things for non-collection monads), but for insertion sort you want to find a position, either swapping places up to that position, or inserting the element at that position. Finding stuff should not be done with for loops or for comprehensions.

Also, there's no pass-by-reference in Scala. And, in fact, Array is not even a Scala collection, but a Java thingy which has unique characteristics granted to it by the JVM that are not reproducible with classes, so it can't be replaced.

here's another generic version of insertion sort:

  def less[T <: Comparable[T]](i: T, j: T) = i.compareTo(j) < 0

  def swap[T](xs: Array[T], i: Int, j: Int) { val tmp = xs(i); xs(i) = xs(j); xs(j) = tmp }

  def insertSort[T <: Comparable[T]](xs: Array[T]) {
    for { i <- 1 to xs.size
          j <- List.range(1, i).reverse
          if less(xs(j),xs(j - 1)) } swap(xs, j, j -1)
  }

What do you need it for?
If you just want a sorted Array I would prefer: def sortArray(a: Array[Int]): Array[Int] = a.sortWith(_ < _).

At the beginning don't forget to add:

import scala.util.control.Breaks._

This is my solution, using a list as an input

def insertionSortLoop(list :List[Int]) : List[Int] = {
      val intArray: Array[Int] = list.toArray
      for ( j <- 1 until intArray.length ) {
          breakable {
            for ( i <- (1 to j).reverse ) {
              if (intArray(i-1) < intArray(i)) {
                break
              } else {
                  val temp = intArray(i)
                  intArray(i) = intArray(i-1)
                  intArray(i-1) = temp
              }
            }
        }
      }
      intArray.toList
    }

I have the implementation here at github.

Here is a code sample written using foldLeft.

def insertionSort(input: List[Int]): List[Int] = {

  input.foldLeft(List[Int]())( (acc, element) => {

    val (firstHalf, secondHalf) = acc.span(_ < element)

    //inserting the element at the right place
    firstHalf ::: element :: secondHalf
  })
}

The example can be found in this github repo.

Even though, when coding Scala, I'm used to prefer functional programming style (via combinators or recursion) over imperative style (via variables and iterations), THIS TIME, for this specific problem, old school imperative nested loops result in simpler code for the reader. I don't think falling back to imperative style is a mistake for certain classes of problems (such as sorting algorithms which usually mutate a buffer of items passed as input rather than resulting to a new sorted collection)

Here it is my solution:

package bitspoke.algo

import scala.math.Ordered
import scala.collection.mutable.Buffer

abstract class Sorter[T <% Ordered[T]] {

  // algorithm provided by subclasses
  def sort(buffer : Buffer[T]) : Unit

  // check if the buffer is sorted
  def sorted(buffer : Buffer[T]) = buffer.isEmpty || buffer.view.zip(buffer.tail).forall { t => t._2 > t._1 }

  // swap elements in buffer
  def swap(buffer : Buffer[T], i:Int, j:Int) {
    val temp = buffer(i)
    buffer(i) = buffer(j)
    buffer(j) = temp
  }
}

class InsertionSorter[T <% Ordered[T]] extends Sorter[T] {
  def sort(buffer : Buffer[T]) : Unit = {
    for {
      i <-  1 until buffer.length
      j <-  i until 0 by -1
      if (buffer(j) < buffer(j - 1))
    }
    swap(buffer, j, j - 1)
  }
}

As you can see, rather than using java.lang.Comparable, I preferred scala.math.Ordered and Scala View Bounds rather than Upper Bounds. That's certainly works thanks to many Scala Implicit Conversions of primitive types to Rich Wrappers.

You can write a client program as follows:

import bitspoke.algo._
import scala.collection.mutable._

val sorter = new InsertionSorter[Int]
val buffer = ArrayBuffer(3, 0, 4, 2, 1)
sorter.sort(buffer)

assert(sorter.sorted(buffer))

Github link to Scala implementation

Pseudo Code:

Algorithm Insertion-Sort-Descending(A)
    for j <- 2 to length[A]
        key <- A[j]                 // element we wish to insert
        i <- j - 1                  // position to the left side
        while i > 0 and A[i] < key  // while has not found correct position <-- difference between Ascending and Descending
            A[i + i] = A[i]         // right shift element
            i = i - 1               // decrement i
        A[i + 1] = key              // found position, place key

The answers of adijo and @RB_ are mostly right, given that you want an immutable implementation of insertion sort.

However those implementations, for lists bigger than around 50.000 entries will blow up the stack with StackOverflow error. This is due to the fact that the recursive methods used there are not @tailrec.

One possible solution is to use CPS to make the method tailrec, as follows:

object Sort {
    def apply[A: Ordering](list: List[A]): List[A] = {
    
        @tailrec
        // In order to make this code tailrec, we are using CPS (continuation passing style)
        def insert(entry: A, list: List[A])(k: List[A] => List[A]): List[A] =
          list match {
            case Nil                       => k(List(entry))
            case head :: _ if entry < head => k(entry :: list)
            case head :: tail              => insert(entry, tail)(r => k(head :: r))
          }

        @tailrec
        def inner(sorted: List[A], rest: List[A]): List[A] =
          rest match {
            case Nil          => sorted
            case head :: tail => inner(insert(head, sorted)(identity), tail)
          }

        inner(Nil, list)
    }
}

Is worth noticing that an immutable implementation is always going to be slower than a mutable one.

From the benchmark results I've made, insertion sort performs around 2.5 times faster with a mutable implementation.