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

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


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

void fusion(int * A, int p, int q, int r){
    int* Ad, Ag;
    memset(Ad, 0, p);
    memset(Ag, 0, q);
    int n1 = q-p;
    int n2 = r-q;
    int indg = 0;
    int indd = 0;
    int 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++;
    }
}