package kapitel_04

/**
 * Beispiel aus
 *
 * - Algorithmen und Datenstrukturen für Dummies
 *   - von Andreas Gogol-Döring und Thomas Letschert
 *   - Verlag Wiley-VCH; Oktober 2019
 *  - Kapitel 4, Listen: Immer einer nach dem anderen
 *
 * @author A. Gogol-Döring, Th. Letschert
 */

object AuD_04_08_InsertionSortFunctionalList_App extends App {

  def insert(a: List[Int], v: Int): List[Int] = a match {
    case Nil =>
      v :: Nil
    case x :: rest if v < x =>
      v :: a
    case x :: rest if v >= x =>
      x :: insert (rest, v)
  }

  def sort(a: List[Int]): List[Int] = a match {
    case Nil => Nil
    case v :: rest => insert(sort(rest), v)
  }

  val lst = List(-1,5,7,7,3,4,-2,3,6,7,-7,9,3,8,5,-1,0,2,3,7,-4,6,5)

  println(sort(lst).mkString(", "))

}