tri_fusion.c

#include <math.h>
#include <stdlib.h>
#include <stdio.h>
#include "tri_fusion.h"

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

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

void copySousTable(long* mainT, long* underT, size_t id, size_t size) {
  for(size_t i = id; i < id+size; ++i) {
    underT[i-id] = mainT[i];
  }
}

void fusion(long* A, size_t first, size_t middle, size_t size) {
    size_t n1 = middle - first; // Nb elem dans A[p , q]  q exclu
    size_t n2 = size - middle;  // Nb elem dans A[q , r]  r exclu

    size_t indg = 0;
    size_t indd = 0;

    long* ag = malloc(sizeof(long) * n1);
    long* ad = malloc(sizeof(long) * n2);

    copySousTable(A, ag, first, n1);
    copySousTable(A, ad, middle, n2);

    int i = first;

    while(i < size) {
      if(indg == n1) {
        A[i] = ad[indd];
        indd++;
      }
      else if(indd == n2) {
        A[i] = ag[indg];
        indg++;
      }
      else if(ag[indg] < ad[indd]) {
        A[i] = ag[indg];
        indg++;
      }
      else {
        A[i] = ad[indd];
        indd++;
      }
      ++i;
    }

    free(ag);
    free(ad);
}