Algorithme Mergesort en Java

Le bogue dans votre code est difficile à repérer:

• la boucle de votre fonction merge itère pour i de 0 à r - l + 1 exclu, ce qui serait correct si r et l restaient constants pendant la boucle, mais vous incrémentez l à chaque fois que vous copiez à partir de la partie gauche, réduisant le nombre d'itérations. En conséquence, la boucle se termine tôt, laissant les éléments restants dans cache_array avec leur valeur par défaut 0 .

Il existe plusieurs sources de confusion dans le code:

• la convention pour inclure r dans la tranche est déroutante: elle nécessite des ajustements +1 / -1 pour calculer les longueurs de tranche et le index du milieu.
• utiliser Math.floor () est inutile: l'arithmétique d'entiers utilise la division d'entiers en java.
• incrémenter les arguments l et m est déroutant car ceux-ci perdent leur signification si la valeur est modifiée. Utilisez d'autres variables d'index pour parcourir les tableaux.
• l'ajout d'un { entre les mots clés else et if introduit des niveaux d'indentation inutiles.
• la dernière condition est l'opposé de la précédente: vous devez simplement l'omettre. Notez que si les éléments du tableau étaient des valeurs à virgule flottante, les deux conditions pourraient être fausses pour les valeurs NaN et certains éléments de cache_array ne seraient pas modifiés. Cette dernière condition entraînerait des erreurs dans ce cas.

Voici une version modifiée:

// merge adjacent slices of the `sort` array.
// left slice has elements from `l` included to `m` excluded
// right slice has elements from `m` included to `r` excluded
static void merge(int[] sort, int l, int m, int r) {
    int len = r - l;
    int[] cache_array = new int[len];
    for (int i = 0, ll = l, mm = m; i < len; i++) {
        if (ll >= m) {
            cache_array[i] = sort[mm];
            mm++;
        } else
        if (mm >= r) {
            cache_array[i] = sort[ll];
            ll++;
        } else
        if (sort[ll] >= sort[mm]) {
            cache_array[i] = sort[ll];
            ll++;
        } else {
            cache_array[i] = sort[mm];
            mm++;
        }
    }
    for (int i = 0; i < len; i++) {
        sort[l + i] = cache_array[i];
    }
}

static void mergeSort(int[] sort, int l, int r) {
    if (r - l > 1) {
        int mid = l + (r - l) / 2;
        mergeSort(sort, l, mid);
        mergeSort(sort, mid, r);
        merge(sort, l, mid, r);
    }
}
    
public static void main(String[] args) {
    int[] a = { 2, 1, 4, 5, 73, 74, 7, 5, 64, 2 };
    mergeSort(a, 0, a.length);
    for (int i : a) {
        System.out.println(i);
    }
}

Je l'implémente généralement comme ceci:

/// <summary>
/// Mergesort
/// best-case: O(n* log(n))
/// average-case: O(n* log(n))
/// worst-case: O(n* log(n))
/// </summary>
/// <returns>The sorted array.</returns>
/// <param name="array">array.</param>
public static int[] MergeSort(int[] array) {
        //  Exit condition for recursion
        if (array.length <= 1) return array;
        //  Middle index of list to sort
        int m = array.length / 2;
        //  Define left and right sub-listså
        int[] left_array = new int[m];
        int[] right_array = new int[array.length - m];
        //  Initialize left list
        for (int i = 0; i < m; i++) left_array[i] = array[i];
        //  Initialize right list
        for (int i = m, x = 0; i < array.length; i++, x++) right_array[x] = array[i];
        //  Recursively sort left half of the list
        left_array = MergeSort(left_array);
        //  Recursively sort right half of the list
        right_array = MergeSort(right_array);
        //  Merge sorted sub-lists
        return Merge(left_array, right_array);
}
/// <summary>
/// Merge the specified left_array and right_array.
/// </summary>
/// <returns>The merge.</returns>
/// <param name="left_array">Left array.</param>
/// <param name="right_array">Right array.</param>
public static int[] Merge(int[] left_array, int[] right_array) {
        int[] m = new int[left_array.length + right_array.length];
        int index_l = 0;
        int nl, nr;
        nl = left_array.length - 1;
        nr = right_array.length - 1;
        for (int i = 0; i <= nl + nr + 1; i++) {
                if (index_l > nl) {
                        m[i] = (right_array[i - index_l]);
                        continue;
                }
                if (index_l < i - nr) {
                        m[i] = (left_array[index_l]);
                        index_l++;
                        continue;
                }
                if (left_array[index_l] <= (right_array[i - index_l])) {
                        m[i] = (left_array[index_l]);
                        index_l++;
                } else {
                        m[i] = (right_array[i - index_l]);
                }
        }
        return m;
}

Il y a quelques mois, j'ai écrit tous les algorithmes de tri courants et c'est ce que j'ai obtenu. Un peu inexact mais juste pour voir comment cette implémentation fonctionne. Les autres algorithmes sont ici.

Pour obtenir un ordre décroissant, je pense qu'il vous suffit d'échanger les opérateurs de comparaison.