합병정렬이란?
분할정복 알고리즘의 하나이며 안정 정렬에 속한다.
과정
- 리스트의 길이가 0또는 1이면 이미 정렬된 것을 본다.
- 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
- 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
- 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.
특징
- 단점
- 만약 레코드를 배열로 구성하면, 임시 배열이 필요
- 레코드들의 크기가 큰 경우에는 이동 횟수가 많으므로 매우 큰 시간적 낭비 초래
- 장점
- 안정적인 정렬 방법
- 만약 레코드를 연결 리스트로 구성하면, 링크 인덱스만 변경되므로 데이터의 이동은 무시할 수 있을 정도로 작아진다.
- 따라서 크기가 큰 레코드를 정렬할 경우에 연결 리스트를 사용한다면, 합병 정렬은 퀵 정렬을 포함한 다른 어떤 정렬 방법보다 효율적이다.
시간복잡도