자료구조,2-Way합병정렬 에 관하여

목차

없음

본문내용

우선 합병정렬이 무엇인지 알아봐야 한다.
퀵 정렬은 데이터를 나누는 과정에서 정렬이 이루지고 합병 정렬은 분할된 데이터를 합치면서 정렬이 이루어진다. 합병 정렬은 정렬이 되어 있는 리스트를 합치면서 정렬하는 방식인데 정렬이 되어 있지 않은 데이터는 내부 정렬을 수행하거나 정렬된 상태가 될 때 까지 분할한 뒤에 정렬을 수행해야 한다. 메모리 공간이 부족 할 때 사용하던 정렬 방식이다.​ 저장 공간도 넉넉하지 않았기 때문에 합병과 분할을 반복적으로 수행하여 정렬하던 방식들이다.
과거와 다르게 현재는 HDD 보다 더 큰 용량의 저장 장치가 없기 때문에 합병 작업 도중에 분할하는 일은 없다. 합병 정렬은 외부 정렬용 알고리즘이지만 [2-way 합병 정렬]은 처리 속도가 빨라서 내부 정렬용으로도 사용 된다. 내부 정렬시 퀵 정렬보다 공간 복잡도는 높고 처리 속도는 느리다.

참고 자료

없음