Mergesort 최적화

Question

병합 정렬은 매우 일반적인 정렬 알고리즘이며 작동하는 병합 정렬 알고리즘을 작성했습니다. 그런 다음 최적화하고 싶습니다. 첫 번째 단계는 그것을 재귀 적 반복에서 반복적 반복으로 변환하는 것이 었습니다. 그렇다면 다른 무엇이 최적화 될 수 있는지를 분별할 수 없었습니다. 인터넷에서 많은 기사를 통해 살펴본 결과, 다중 병합 정렬과 타일링 된 병합 정렬을 사용하는 두 가지 메커니즘이 있습니다. 그러나 모든 의사 코드를 제공 한 문서는 없으며 캐시 작성 방법에 많은 부분을 설명하는 데 신경 쓰지 않았으며 작성자가 말하는 장점에 대해 캐시 친화적이고 향상된 지역 성과와 같은 이점을 어떻게 제공합니까?

누구든지이 문제에 대해 자세히 설명하고 가능하면 의사 코드를 제공 할 수 있습니까? 특히, 캐시 친화적 인 방법을 알고 싶습니다. 나는이 물건이 무엇인지에 관해 전혀 모른다. 그렇지 않으면 나는 그것을 나 자신으로 시험해 보았다.

Answer 1

하위 배열 크기가 특정 임계 값보다 낮 으면 mergesort에서 삽입 정렬과 같은 다른 알고리즘으로 전환 할 수 있습니다. mergesort가 O (n log n) 시간에 실행되지만, 장기 성장률에 대해 이야기하고 알고리즘이 작은 입력에서 얼마나 잘 수행되는지에 대해서는 언급하지 않습니다. 예를 들어 삽입 정렬은 비록 장기적으로는 더 나빠도 작은 입력 크기에서 매우 빠르게 실행됩니다. 따라서 정렬 할 배열이 특정 크기 임계 값 (예 : 50-100)보다 작 으면 재귀를 계속할 때가 아니라 삽입 정렬을 사용하도록 mergesort의 기본 대/소문자를 변경하는 것이 좋습니다. 경험상 알고리즘의 성능이 크게 향상 될 수 있습니다.