입력 데이터에 상관 없이 일정한 속도를 보여주는 정렬 방법
분할정복
합병 정렬은 분할정복을 사용하여 전체 원소가 아닌 부분 집합으로 분리 한후, 부분집합에 대해 정렬을 수행합니다. 정렬한 부분끼리 다시 결합하여 정렬을 수행합니다.
정렬 과정
출처 : https://www.podo-dev.com/blogs/74
- 배열의 길이가 0 또는 1이라면 정렬된 것으로 판단합니다. 아닌 경우에는
- 정렬되지 않은 배열을 절반으로 나눈다.
- 나누어진 배열을 재귀를 이용하여 합병정렬한다.
- 두 부분을 다시 하나로 합친다
장단점
- 입력 데이터에 상관없이 항상 nlogN의 속도로 동작한다.
- 메모리를 다른 정렬에 비해 많이 사용한다.
시간 복잡도
