Meilleure réponse
Le tri par fusion, sil est implémenté pour créer des tableaux dans les appels récursifs, créera beaucoup dentre eux, mais ils ne coexisteront pas en même temps. Dans chaque appel récursif, vous créez un tableau (ou 2 selon une implémentation) pour la fusion et ils ne prennent pas plus de O (n) espace, puis lorsque la fusion est fait, ces tableaux sont supprimés et de nouveaux seront créés après un moment dans un autre appel récursif. Si vous avez compté lespace pris par tous les tableaux qui ont été créés, ce serait O (n log n), mais vous navez pas besoin de vous soucier de ces informations – vous navez pas besoin de plus de O (n) espace, car lorsque vous avez besoin de créer un tableau, tous les autres nexistent plus et noccupent pas de mémoire . Notez que vous pouvez simplement déclarer 2 – ou 3 – tableaux au début, chacun la longueur de n, puis stocker la séquence dans lun deux, tout en utilisant lautre pour fusionner, cela améliorera les performances et vous montrera au-delà Je doute quil ny ait pas besoin de plus de O (n) de mémoire.
Réponse
Lors du tri par fusion, lorsque nous fusionnons les 2 tableaux triés, nous créons 2 tableaux temporaires. L [ ] = Arr [gauche, milieu] (tableau de gauche) pour stocker temporairement lancien tableau de gauche à milieu (moitié gauche triée) et R [] = Arr [milieu + 1, droite] (tableau de droite) pour stocker temporairement lancien tableau du milieu + 1 à la droite (triée moitié droite), puis nous fusionnons les deux tableaux temporaires dans le tableau dorigine. Le fait que nous créons 2 tableaux temporaires pour stocker les numéros du tableau dorigine, puisque le tableau dorigine a n éléments le temporaire les tableaux sont de taille n respectivement et donc lespace supplémentaire de n et une complexité despace O (n). Lespace dorigine du tableau nest pas pris en compte lors du calcul de la complexité spatiale dune sorte algorithme.