A chaque niveau, on effectue des tris de taille M sur un certain nombre de tranches/blocs
Role de chaque fonction
ipow(a, b) : calcule a^b par multiplications successives.
cmp_int(a, b) : comparateur d'entiers pour qsort (retourne l'ordre).
reorder_blocks(base, block_sz, M, idx) : reordonne, dans un groupe de M blocs contigus de taille block_sz,
l'ordre des blocs selon le tableau d'indices idx (via un tampon temporaire).
sort_ND(a, N, M) :
- trie chaque sous-tableau 1D de longueur M (dimension la plus basse)
pour chaque niveau 2...N, calcule la somme de chaque bloc de la dimension inferieure, trie les blocs selon ces sommes, puis rerdonne physiquement les blocs.
Etant donne que notre parcours se fait sur le nombre d'element a parcourir dans chaque dimensions (c'est M), et que ce parcour on doit le faire sur chaque dimensions
On a donc M^N (M puissance N) comme complexite algorithmique.
