Cel mai bun răspuns
Mergesort, dacă este implementat pentru a crea tablouri în apelurile recursive, va crea multe dintre ele, dar nu vor coexista în același timp. În fiecare apel recursiv, creați o matrice (sau 2 în funcție de o implementare) pentru fuzionare și nu ocupă mai mult decât O (n) spațiu, și atunci când fuzionarea este terminat, aceste matrice sunt șterse și unele noi vor fi create după un moment în alt apel recursiv. Dacă ați numărat cât spațiu au luat toate matricile care au fost create vreodată, ar fi O (n log n), dar nu trebuie să vă pese de aceste informații – nu aveți nevoie de mai mult de O (n) spațiu, deoarece atunci când trebuie să creați o matrice, toate celelalte nu mai există și nu ocupă nicio memorie . Rețineți că puteți declara pur și simplu 2 – sau 3 – matrice la început, fiecare având lungimea lui n, și apoi să stocați secvența într-una dintre ele, în timp ce o folosiți pe cealaltă pentru îmbinare, aceasta va îmbunătăți performanța, precum și vă va arăta dincolo îndoială că nu este nevoie de mai mult de O (n) de memorie.
Răspuns
În sortarea prin îmbinare când combinăm matricea sortată cu 2, creăm 2 matrice temporare. L [ ] = Arr [stânga, mijloc] (matrice stânga) pentru a stoca temporar matricea veche de la stânga la mijloc (sortată la jumătatea stângă) și R [] = Arr [mijloc + 1, dreapta] (matrice dreapta) pentru a stoca temporar matricea veche de la mijlocul + 1 la dreapta (sortat jumătatea dreaptă), apoi îmbinăm cele două matrice temporare în cea originală. Faptul că creăm 2 matrice temporare pentru a stoca numerele matricei originale, deoarece matricea originală are n elemente temporare matricile sunt de dimensiunea n și, prin urmare, spațiul suplimentar al lui n și o complexitate spațială O (n). Spațiul original al matricei nu este contabilizat în timp ce se calculează complexitatea spațiului unui sort ing algoritm.