package kapitel_07

/**
 * Beispiel aus
 *
 * - Algorithmen und Datenstrukturen für Dummies
 *   - von Andreas Gogol-Döring und Thomas Letschert
 *   - Verlag Wiley-VCH; Oktober 2019
 *  - Kapitel 7, Sortieren
 *
 * @author A. Gogol-Döring, Th. Letschert
 */

import scala.reflect.ClassTag

object AuD_07_03_Mergesort_App extends App {

  /*
   * Der Classtag wird benötigt, um ein Array vom korrekten typ zu erzeugen. (Array in der JVM haben ein Class-Tag)
   */

  def MergeSort[A: Ordering](a: Array[A], l: Int, r: Int)(implicit ct: ClassTag[A]) : Unit = {
    if (l < r) {
      val m: Int = (l + r + 1) / 2 // AUF-gerundete ganzahlige Division !
      MergeSort(a, l, m - 1)
      MergeSort(a, m, r)
      Merge(a, l, m, r)
    }

    def Merge(a: Array[A], l: Int, m: Int, r: Int): Unit = {
      val b = new Array[A](a.length)  // hier wird der Classtag gebraucht
      var i_l = l
      var i_r = m
      var j = l
      while (i_l < m || i_r <= r) {
        if ( i_r > r || (i_l < m) && implicitly[Ordering[A]].lteq(a(i_l), a(i_r)) ) {
          b(j) = a(i_l)
          i_l = i_l + 1
        } else {
          b(j) = a(i_r)
          i_r = i_r + 1
        }
        j = j + 1
      }
      for (i <- l to r) {
        a(i) = b(i)
      }
    }
  }

  val aInt = Array(13, 7, 9, 12, 3, 7, 30, 2, 8, 12)
  MergeSort(aInt, 0, aInt.length - 1)
  println(aInt.mkString(", "))

}