/**
 * 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 Foundation

struct AuD_07_03_Mergesort {

    static func MergeSort<A: Comparable>(a: inout [A], l: Int, r: Int) {

        func Merge(l: Int, m: Int, r: Int) {
            var b = [A](repeating: a[0], count: a.count)
            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) && (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 in l ... r {
                a[i] = b[i]
            }
        }

        if (l < r) {
            let m: Int = (l + r + 1) / 2 // AUF-gerundete ganzahlige Division !
            MergeSort(a: &a, l: l, r: m - 1)
            MergeSort(a: &a, l: m, r: r)
            Merge(l: l, m: m, r: r)
        }

    }

    static func run () {
        var aInt = [13, 7, 9, 12, 3, 7, 30, 2, 8, 12]
        MergeSort(a: &aInt, l: 0, r: aInt.count - 1)
        print(aInt.map( { s in s.description} ) . joined(separator: ", "))
    }
}