merge sort에서 3-way 보다 2-way 를 더 많이 쓰는 이유

소개글

합병정렬을 하는 과정에서 주어진 배열을 반 으로 나누지 않고 그 이상으로 나눌 수도 있는데
왜 반으로 나누는 것을 더 많이 선호하는지에 대한 기술입니다.

주어진 자료를 절반 이상으로 나눠 정렬하는 방식의 대표로서 3-way merge sort 를 언급하였고,
2-way 와 3-way 각각에서 시간, 중복, 구현 세 가지 측면에서 비교하였습니다.

두 방식에서의 시간소요, 중복이 발생하는 횟수 등은 수식을 통해 비교를 시도하였고,
구현측면에서의 비교는 재귀호출을 통한 DnC 알고리즘을 동일하게 사용한 두 방식의 소스코드를
통해 직관적인 비교를 하였습니다.

문서 말미에는 결론도출을 시도하여 다른 방식보다 2-way 를 더 선호하는 이유를 기술하였습니다.
->2010.03.18 문서 개편 후 재업로드( V 2.0 ).
->2010.03.15 내용수정후 재업로드( V 1.1 ).

목차

◎ 주어진 문제 : k-way merge sort 에서 k=3보다 k=2를 더 많이 쓰는 이유는?

본문내용

정렬해야 하는 자료의 크기가 커지면 커질수록 궁극적으로는 3-way merge sort 가 2-way merge sort 보다 소요되는 시간이 적게 나올수도 있지만 2-way merge sort 의 정렬소요시간이 불합리할 만큼 큰 시간은 아니며, 자료의 크기에 비례하여 중복연산되는 원소들의 개수가 증가하여 소스코드의 구현도 더 복잡하여 유지/보수가 어려워질 것이다. 이와 같은 세 가지 양상들은 N-way merge sort 를 구현하고자 하는 경우 더욱더 부각되어나갈 것이다.

참고 자료

없음