Bedste svar
Mergesort, hvis det implementeres for at oprette arrays i de rekursive opkald, vil skabe mange af dem, men de vil ikke eksistere samtidig. I hvert rekursivt opkald opretter du et array (eller 2 afhængigt af en implementering) til fletning, og de tager ikke mere end O (n) plads, og derefter når fletningen er gjort, disse arrays slettes, og nogle nye oprettes efter et øjeblik i et andet rekursivt opkald. Hvis du tæller, hvor meget plads alle arrays, der nogensinde er oprettet, tog, ville det være O (n log n), men du behøver ikke være ligeglad med disse oplysninger – du behøver ikke mere end O (n) plads, for når du har brug for at oprette en matrix, eksisterer alle de andre ikke længere og optager ikke nogen hukommelse . Bemærk, at du simpelthen kan erklære 2 – eller 3 – arrays i begyndelsen, hver længde på n, og derefter gemme sekvensen i en af dem, mens du bruger den anden til at flette, det forbedrer ydeevnen samt viser dig ud over tvivl om, at der ikke er behov for mere end O (n) hukommelse.
Svar
I flettsortering når vi fletter det 2 sorterede array opretter vi 2 midlertidige array. L [ ] = Arr [venstre, midt] (venstre matrix) for midlertidigt at gemme den gamle matrix fra venstre til midten (sorteret venstre halvdel) og R [] = Arr [midt + 1, højre] (højre matrix) for midlertidigt at gemme den gamle matrix fra midten + 1 til højre (sorteret til højre halvdel), så fletter vi de to midlertidige array sammen med den oprindelige. Det faktum, at vi opretter 2 midlertidige array til at gemme numrene på den originale array, da den originale array har n elementer den midlertidige arrays har henholdsvis størrelse n og dermed den ekstra plads af n og en O (n) rumkompleksitet. Det oprindelige rum i arrayet tages ikke med i beregningen af en komplekses rumkompleksitet ing-algoritme.