Listes scala, tri et fusion (tri insertion et rapide)

// ****** J'ai posté ceci pour les futurs élèves qui devront faire des algorithmes de ce genre en classe :D ******
// ****** Comme ça, c'est EASY le Scala \o/ ******

// Tri par insertion (Scala) :

// Tri par insertion d'un élément :
def insere(elem: Int, liste: List[Int]): List[Int] = {
    liste match {
        case Nil => elem::Nil // Transforme en liste
        case head::tail =>
        if ( elem < head ) {
            elem::liste
        } else {
            head::insere(elem,tail)
        }
    }
}
// On utilise la dernière fonction pour trier une fonction (par insertion) :
def tri(liste: List[Int]): List[Int] = {
    liste match {
        case Nil => liste
        case head::tail => insere(head,tri(tail))
    }
}
// Tri par insertion d'un élément avec le choix de l'ordre à mettre en condiion :
// Exemple d'appel de la fonction :
//      insere(0,List(1,2,3),(x,y)=>x<y)
def insere(elem: Int, liste: List[Int], less: (Int,Int) => Boolean): List[Int] = {
    liste match {
        case Nil => elem::Nil
        case head::tail =>
        if ( less(elem,head) ) {
            elem::liste
        } else {
            head::insere(elem,tail,less)
        }
    }
}
// Tri décroissant par insertion. On utilise la dernière fonction :
def triDecroissant(liste: List[Int]): List[Int] = {
    liste match {
        case Nil => liste
        case head::tail => insere(head,triDecroissant(tail),(x,y)=>x>y)
    }
}

// Fusion de listes triées (Scala) :

def fusion(list1: List[Int], list2: List[Int]): List[Int] = {
    (list1,list2) match { // On regarde si list1 est vide :
        case (Nil,list2) => list2 // On renvoie list2 si list1 est vide
        case (list1,Nil) => list1 // Et on renvoie list1 si list2 est vide
        case (head1::tail1,head2::tail2) => // Sinon :
        if ( head1 < head2 ) { // Si la tête de list1 est inférieure à la tête de list2 :
            head1::fusion(tail1,list2) // On renvoie la tête de list1 concaténée au reste des listes
        } else {
            head2::fusion(list1,tail2) // On renvoie la tête de list2 concaténée au reste des listes
        }
    }
}

// Tri rapide (Scala) :

def sort(xs: Array[Int]) {
    def swap(i: Int, j: Int) {
        val t = xs(i); xs(i) = xs(j); xs(j) = t
    }
    def sort1(l: Int, r: Int) {
        val pivot = xs((l + r) / 2)
        var i = l; var j = r
        while (i <= j) {
            while (xs(i) < pivot)
                i += 1
            while (xs(j) > pivot)
                j -= 1
            if (i <= j) {
                swap(i, j)
                i += 1
                j -= 1
            }
        }
        if (l < j)
            sort1(l, j)
        if (j < r)
            sort1(i, r)
    }
    sort1(0, xs.length - 1)
}