#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);
}

void sousTriRapide(long* A, size_t p, size_t r) {
    if (p<r-1) {
        size_t q = partition(A, p, r);
        sousTriRapide(A, p, q);
        sousTriRapide(A, q+1, r);
    }
}

size_t partition(long* A, size_t p, size_t r) {
    size_t pivot = A[r-1];
    size_t i = p;
    long temp;
    for (size_t j = p; j < r-2; j++) {
        if (A[j] <= pivot) {
            temp = A[i];
            A[i] = A[j];
            A[j] = temp;
            i++;
        }
    }
    temp = A[i];
    A[i] = A[r-1];
    A[r-1] = temp;
    return i;
}

void triRapide(long* A, size_t n) {
    sousTriRapide(A, 0, n);
}