Comprendre la récursion de mergesort

FUSION SORT:

1) Diviser le tableau en deux

2) Trier la moitié gauche

3) Trier la moitié droite

4) Fusionner les deux moitiés ensemble

une chose évidente à faire serait d'essayer cette sorte de fusion sur un petit tableau, disons taille 8 (Puissance de 2 est pratique ici), sur papier. Faites comme si vous étiez un ordinateur qui exécute le code, et voyez s'il commence à devenir un peu plus clair.

votre question est un peu ambiguë parce que vous n'expliquez pas ce que vous trouvez confus, mais il semble que vous essayez de dérouler les appels récursifs dans votre tête. Qui peut ou peut ne pas être une bonne chose, mais je pense qu'il peut facilement conduire à avoir trop bien dans votre tête à la fois. Au lieu d'essayer de tracer le code du début à la fin, voyez si vous pouvez comprendre le concept abstraitement. Fusion de tri:

1. Divise le tableau en deux
2. Trie la moitié gauche
3. Trie la moitié droite
4. Fusionne les deux moitiés ensemble

(1) devrait être assez évident et intuitif pour vous. Pour l'étape (2) l'idée clé est présent, la moitié gauche d'un tableau... est un tableau. en Supposant que votre fusion tri fonctionne, il doit être capable de classer la moitié gauche du tableau. Droit? Step (4) est en fait une partie assez intuitive de l'algorithme. Un exemple devrait la rendre insignifiante:

at the start
left: [1, 3, 5], right: [2, 4, 6, 7], out: []

after step 1
left: [3, 5], right: [2, 4, 6, 7], out: [1]

after step 2
left: [3, 5], right: [4, 6, 7], out: [1, 2]

after step 3
left: [5], right: [4, 6, 7], out: [1, 2, 3]

after step 4
left: [5], right: [6, 7], out: [1, 2, 3, 4]

after step 5
left: [], right: [6, 7], out: [1, 2, 3, 4, 5]

after step 6
left: [], right: [7], out: [1, 2, 3, 4, 5, 6]

at the end
left: [], right: [], out: [1, 2, 3, 4, 5, 6, 7]

donc en supposant que vous comprenez (1) et (4), une autre façon de penser à une sorte de fusion serait celle-ci. Imaginez quelqu'un d'autre a écrit mergesort() et si vous êtes sûr qu'il fonctionne. Vous pourriez alors utiliser cette implémentation de mergesort() pour écrire:

sort(myArray)
{
    leftHalf = myArray.subArray(0, myArray.Length/2);
    rightHalf = myArray.subArray(myArray.Length/2 + 1, myArray.Length - 1);

    sortedLeftHalf = mergesort(leftHalf);
    sortedRightHalf = mergesort(rightHalf);

    sortedArray = merge(sortedLeftHalf, sortedRightHalf);
}

Notez que sort ne pas utiliser la récursivité. Ça dit juste "trier les deux moitiés et les fusionner". Si vous avez compris l'exemple de fusion ci-dessus, alors j'espère que vous voyez intuitivement que cela sort la fonction semble faire ce qu'elle dit... sorte.

Maintenant, si vous regardez plus attentivement... sort() regarde à peu près exactement comme mergesort()! C'est parce que c'est mergesort() (sauf qu'il n'a pas de cas de base parce qu'il n'est pas récursif!).

mais c'est comme ça que j'aime penser à récursif fonctions: supposons que la fonction fonctionne, quand vous l'appelez. Traitez-le comme une boîte noire qui fait ce dont vous avez besoin. Lorsque vous effectuez cette hypothèse, à comprendre comment remplir cette boîte noire est souvent facile. Pour une entrée donnée, vous pouvez le décomposer en petites entrées pour nourrir votre boîte noire? Après avoir résolu cela, la seule chose qui reste est de gérer les cas de base au début de votre fonction (qui sont les cas où vous n'avez pas besoin de faire des appels récursifs. Par exemple, mergesort([]) juste renvoie un tableau vide; il ne fait pas d'appel récursif à