0
"Introduction to Algorithms"에서 병합 정렬 알고리즘은 MERGE(A, p, q, r)이라는 도우미 함수로 구현되어 이전에 두 개의 정렬 된 시퀀스를 병합합니다.병합 정렬 : 추가 배열 복사본이 필요합니까?
이 함수는 두 개의 추가 배열 L 및 R을 도입합니다.
MERGE(A, p, q, r)
1 n1 ← q − p + 1
2 n2 ←r − q
3 create arrays L[1 . . n1 + 1] and R[1 . . n2 + 1]
.....
"create arrays L[1 . . n1 + 1] and R[1 . . n2 + 1]" 나는 둘 다에 대해 추가 메모리를 할당하는 것으로 알고 있습니다.
이 함수를 다시 쓰면 추가 메모리가 필요없고 A에 직접 작업 할 수 있습니까?
이 질문도 참조하십시오. http://stackoverflow.com/questions/2571049/how-to-sort-in-place-using-the-merge-sort-algorithm –