Beste antwoord
Samenvoegen, indien geïmplementeerd om arrays te maken in de recursieve aanroepen, zal veel van hen, maar ze kunnen niet tegelijkertijd naast elkaar bestaan. In elke recursieve aanroep maak je een array (of 2 afhankelijk van een implementatie) om samen te voegen en ze nemen niet meer dan O (n) spatie in beslag, en wanneer het samenvoegen klaar is, worden deze arrays verwijderd en worden er enkele nieuwe gemaakt na een moment in een andere recursieve aanroep. Als je hebt geteld hoeveel ruimte alle arrays die ooit zijn gemaakt, in beslag hebben genomen, zou het O (n log n) zijn, maar je hoeft je niet druk te maken om deze informatie – je hebt niet meer dan O (n) ruimte nodig, want als je een array moet maken, bestaan alle andere niet meer en nemen ze geen geheugen in beslag . Merk op dat u in het begin eenvoudig 2 – of 3 – arrays kunt declareren, elk met de lengte van n, en vervolgens de reeks in een van hen kunt opslaan, terwijl u de andere gebruikt om samen te voegen, het zal de prestaties verbeteren en u verder laten zien twijfel er niet aan dat er niet meer dan O (n) geheugen nodig is.
Antwoord
Bij het samenvoegen sorteren wanneer we de 2 gesorteerde array samenvoegen, creëren we 2 tijdelijke arrays. L [ ] = Arr [left, mid] (linker array) om de oude array tijdelijk van links naar midden op te slaan (linkerhelft gesorteerd) en R [] = Arr [mid + 1, right] (rechter array) om de oude array tijdelijk op te slaan van midden + 1 naar rechts (gesorteerde rechterhelft), dan voegen we de twee tijdelijke arrays samen met de oorspronkelijke. Het feit dat we 2 tijdelijke arrays maken om de nummers van de oorspronkelijke array op te slaan, aangezien de originele array n elementen heeft, is de tijdelijke arrays hebben respectievelijk de grootte n en dus de extra ruimte van n en een O (n) ruimtecomplexiteit. De oorspronkelijke ruimte van de array wordt niet meegerekend bij het berekenen van de ruimtecomplexiteit van een soort ing algoritme.