Najlepsza odpowiedź
Scalanie, jeśli zaimplementowane jest do tworzenia tablic w wywołaniach rekurencyjnych, utworzy wielu z nich, ale nie będą one współistnieć w tym samym czasie. W każdym wywołaniu rekurencyjnym tworzysz tablicę (lub 2 w zależności od implementacji) do scalania i zajmują one nie więcej niż O (n) miejsca, a następnie, gdy łączenie jest zrobione, tablice te są usuwane, a po chwili w innym wywołaniu rekurencyjnym zostaną utworzone nowe. Jeśli policzysz, ile miejsca zajmowały wszystkie tablice, które kiedykolwiek zostały utworzone, byłoby to O (n log n), ale nie musisz przejmować się tą informacją – nie potrzebujesz więcej niż O (n) miejsca, ponieważ kiedy potrzebujesz stworzyć tablicę, wszystkie inne już nie istnieją i nie zajmują żadnej pamięci . Zwróć uwagę, że możesz po prostu zadeklarować 2 – lub 3 – tablice na początku, każda o długości n, a następnie zapisać sekwencję w jednej z nich, podczas gdy użycie drugiej do scalania poprawi wydajność, a także pokaże poza wątpię, że nie potrzeba więcej niż O (n) pamięci.
Odpowiedź
W sortowaniu przez scalanie, kiedy łączymy 2 posortowane tablice, tworzymy 2 tymczasowe tablice. L [ ] = Arr [left, mid] (lewa tablica), aby tymczasowo zapisać starą tablicę od lewej do połowy (posortowana lewa połowa) i R [] = Arr [mid + 1, right] (prawa tablica), aby tymczasowo zapisać starą tablicę od środka + 1 do prawej (posortowana prawa połowa), następnie łączymy dwie tymczasowe tablice z oryginalną. Fakt, że tworzymy 2 tymczasowe tablice do przechowywania numerów oryginalnej tablicy, ponieważ oryginalna tablica ma n elementów tymczasowa tablice mają odpowiednio rozmiar n, stąd dodatkowa przestrzeń n i złożoność przestrzeni O (n). Oryginalna przestrzeń tablicy nie jest uwzględniana podczas obliczania złożoności przestrzeni pewnego rodzaju algorytm ing.