#include "algos.h"
#include <string.h>

void triInsertion(long* A, size_t n){
    long cle = 0;
    for(size_t i = 1; i<n; i++){
        cle=A[i];
        size_t j = i - 1;
        while (j >= 0 && A[j] > cle){
            A[j+1] = A[j];
            j = j-1;
        }
        A[j+1] = cle;
    }
}


void sousTriFusion(long * A, size_t p, size_t r){
    if(p<r-1){
        size_t q = (size_t)(p+r/2);
        sousTriFusion(A, p, q);
        sousTriFusion(A, q, r);
        fusion(A, p, q, r);
    }
}

void fusion(long * A, size_t p, size_t q, size_t r){
    long* Ad;
    long* Ag;
    size_t n1 = q-p;
    size_t n2 = r-q;
    size_t indg = 0;
    size_t indd = 0;
    size_t i = p;
    while (i < r){
        if(indg == n1){
            A[i] = Ad[indd];
            indd++;
        }
        else if(Ad[indd] == n2){
            A[i] == Ag[indg];
            indg++;
        }
        else if(Ag[indg] < Ad[indd]){
            A[i] = Ag[indg];
            indg++;
        }
        else{
            A[i] = Ad[indd];
            indg++;
        }
        i++;
    }
}

void triFusion(long * A, size_t n){
    sousTriFusion(A, 0, n);
}