Prépa Code Connexion Inscription

On adopte dans cet exercice la convention suivante pour représenter un tableau d'entiers :

• la case 0 contient la taille logique n du tableau,
• les cases 1, 2, ..., n contiennent les n éléments du tableau, triés par ordre croissant,
• les cases au-delà de t.(0) (s'il y en a) contiennent des valeurs sans signification.

Autrement dit, la taille réelle (au sens d'Array.length) peut être supérieure à n+1 : seul le préfixe t.(1) ... t.(t.(0)) a un sens. Un tableau logiquement vide est représenté par [|0|].

Exemple. Le tableau

[| 3 ; 1 ; 4 ; 7 ; 99 ; -2 ; 0 |]

est de longueur 7 au sens d'Array.length, mais sa case 0 vaut 3 : il représente donc la séquence triée 1, 4, 7 (cases 1 à 3). Les cases 4, 5, 6 contiennent 99, -2, 0 mais sont à ignorer — elles ne font pas partie du tableau logique.

Écrire une fonction fusion : int array -> int array -> int array qui prend deux tableaux t1 et t2 au format ci-dessus et renvoie un nouveau tableau au même format, contenant tous les éléments de t1 et de t2, triés par ordre croissant.

On garde toutes les répétitions : si un même entier x apparaît a fois dans t1 et b fois dans t2, il apparaîtra a + b fois dans le résultat. La taille logique du résultat est donc t1.(0) + t2.(0).

Le tableau renvoyé n'aura pas de cases inutilisées en queue.