본 글은 #draft 상태입니다.
- 그림 추가
- 예제 코드 추가
가 뭔데?
- Divide-and-conquer 를 이용한 sort 방식이다.
- 원하는 배열을 정렬되어 있는 배열들의 집합으로 나눈 다음, 이것을 합치는 방식으로 진행된다.
- 이것을 좀 더 구체적으로 확인해 보자.
1. Divide
- 배열을 절반으로 잘라 두개의 배열로 만든다.
- 이 과정을 배열의 원소가 하나가 될 때까지 재귀적으로 반복한다.
2. Merge
- 우선, 원소가 하나인 배열은 정렬되어 있다고 간주한다.
- 두 정렬된 배열을 합치는 것은 two-pointer 로 수행한다.
- 일단 두 정렬된 배열의 크기 총합과 같은 크기의 배열을 하나 준비한다.
- 두 정렬된 배열의 맨 앞에 pointer 를 하나씩 두고,
- 두 pointer 가 가리키는 값 중 같거나 작은 값을 준비한 배열에 넣는다.
- 추가한 뒤에는 해당 pointer 를 하나 움직인다.
- 모든 pointer 가 두 배열의 끝까지 가게 되면 준비한 배열에는 모든 값이 정렬되어 들어가게 된다.
장단점
장점
- 장점은 시간복잡도가 이라는 것이다.
- Divide 에 소요되는 시간이 이고
- Merge 에 소요되는 시간이 이므로
단점
- 단점은 추가적인 배열이 필요하기 때문에 공간복잡도가 높다는 것이다.