Paras vastaus
Jos yhdistäminen toteutetaan rekursiivisten puheluiden taulukoiden luomiseksi, se luo monet niistä, mutta niitä ei tule olemaan samanaikaisesti. Jokaisessa rekursiivisessa puhelussa luot matriisin (tai 2 toteutuksesta riippuen) yhdistämistä varten ja ne vievät enintään O (n) tilaa ja sitten, kun yhdistäminen on valmis, nämä taulukot poistetaan ja jotkut uudet luodaan hetken kuluttua jossakin muussa rekursiivisessa puhelussa. Jos laskit, kuinka paljon tilaa kaikki koskaan luodut matriisit vievät, se ”d on O (n log n), mutta sinun ei tarvitse välittää näistä tiedoista – et tarvitse enempää kuin O (n) tilaa, koska kun sinun on luotava taulukko, kaikkia muita niitä ei enää ole ja ne eivät vie mitään muistia . Huomaa, että voit yksinkertaisesti ilmoittaa alussa 2 – tai 3 – taulukkoa, joista kukin on n: n pituinen, ja tallentaa sitten sekvenssin yhteen niistä, kun taas toista käytetään yhdistämiseen, se parantaa suorituskykyä ja näyttää sinut pidemmälle epäilen, että muistia ei tarvita enempää kuin O (n).
Vastaus
Yhdistämislajittelussa, kun yhdistämme 2 lajiteltua taulukkoa, luomme 2 väliaikaisen taulukon. L [ ] = Arr [vasen, keskellä] (vasen taulukko) tallentaaksesi vanhan ryhmän väliaikaisesti vasemmalta puolelle (lajiteltu vasen puoli) ja R [] = Arr [keskiosa + 1, oikea] (oikea taulukko) tallentaaksesi vanhan ryhmän väliaikaisesti keskeltä + 1 oikealle (lajiteltu oikealle puoliskolle), sitten yhdistämme kaksi väliaikaista taulukkoa alkuperäiseksi. Tosiasia, että luomme 2 väliaikaista taulukkoa alkuperäisen taulukon numeroiden tallentamiseksi, koska alkuperäisessä taulukossa on n elementtiä väliaikainen matriisit ovat kooltaan n ja siten ylimääräinen avaruus n ja O (n) avaruuden monimutkaisuus.Ryhmän alkuperäistä tilaa ei oteta huomioon laskettaessa eräänlaisen tilan monimutkaisuutta algoritmi.