Пространственная сложность сортировки слиянием в неизменяемом массиве

Question

Пространственная сложность сортировки слиянием O(n) и метод выглядит void sort(int[] arr),

Если я создаю метод int[] sort(int[] arr), который не изменяет входной массив, но возвращает новый отсортированный, то какова будет сложность пространства этого метода / алгоритма?

Answer 1

Зависит от реализации сортировки слиянием.

рекурсивный

Поскольку вы не можете изменить входной массив в каждом рекурсивном вызове, пространственная сложность алгоритма S(n) = 2S(n/2) + n, Следовательно, S(n) = Theta(n log n),

итеративный

Если реализация сортировки слиянием не является рекурсивной (итеративная сортировка слиянием), вы можете скопировать входной массив в изменяемый массив и отсортировать этот массив на месте. Следовательно, сложность пространства этой реализации сортировки слиянием Theta(n),