최상 답변
Mergesort는 재귀 호출에서 배열을 생성하도록 구현 된 경우 다음을 생성합니다. 많은 것들이 동시에 공존하지는 않을 것입니다. 모든 재귀 호출에서 병합을위한 배열 (또는 구현에 따라 2 개)을 만들고 O (n) 공간 만 차지한 다음 병합 할 때 이 작업이 완료되면 이러한 어레이가 삭제되고 일부 다른 재귀 호출에서 잠시 후에 일부 새 어레이가 생성됩니다. 생성 된 모든 어레이가 차지한 공간을 계산하면 “O (n log n)”가됩니다. 하지만이 정보에 대해 신경 쓸 필요는 없습니다. O (n) 공간 이상이 필요하지 않습니다. 배열을 생성해야 할 때 다른 모든 배열이 더 이상 존재하지 않고 메모리를 차지하지 않기 때문입니다. . 처음에 2 개 또는 3 개 배열을 선언하고 각각 길이가 n 인 다음 그 중 하나에 시퀀스를 저장하고 병합을 위해 다른 하나를 사용하면 성능이 향상되고 그 이상을 보여줄 수 있습니다. O (n) 이상의 메모리가 필요하지 않습니다.
Answer
2 개의 정렬 된 배열을 병합 할 때 병합 정렬에서 2 개의 임시 배열을 만듭니다. L [ ] = Arr [left, mid] (left array)는 기존 배열을 왼쪽에서 중간 (왼쪽으로 정렬 됨)으로 임시 저장하고 R [] = Arr [mid + 1, right] (right array)는 임시로 기존 배열을 저장합니다. mid + 1에서 right (sorted right half)로, 그런 다음 두 개의 임시 배열을 원래 배열로 병합합니다. 원래 배열에 n 개의 요소가 있으므로 원래 배열의 번호를 저장하기 위해 2 개의 임시 배열을 생성한다는 사실 배열은 각각 크기가 n이므로 n의 추가 공간과 O (n) 공간 복잡성이 있습니다. 정렬의 공간 복잡성을 계산하는 동안 배열의 원래 공간은 고려되지 않습니다. ing 알고리즘.