바킹독(https://www.youtube.com/@BaaaaaaaaaaaaaaaaaaaaarkingDog)님의 영상을 참고했습니다.
합병 정렬(Merge Sort)은 폰 노이만이 제안한 방법으로
일반적인 방법으로 구현했을 때, 이 정렬은 안정 정렬(Stable Sort)에 속하며 분할 정복 알고리즘(Divide and conquer algorithm)의 하나이다
안정 정렬: 정렬 이후에도 같은 key 값을 가진 원소들의 순서가 유지되는 정렬을 의미한다.
예를들어 그림에서 파란옷, 빨간옷, 초록옷은 모두 21로 우선순위가 동일하다. 불안정 정렬에서는 같은 우선순위의 원소끼리의 순서를 보장하지 않는 반면 안정된 정렬에서는 처음 순서를 유지해야하므로 가장 오른쪽 위의 파란옷, 빨간옷, 초록옷 순서의 정렬만 안정 정렬이라고 말한다.
분할 정복 알고리즘: 문제를 작은 문제로 분리하고 각각을 해결한 다음 결과를 모아서 원래 문제를 해결하는 전략
합병 정렬 과정
- 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 본다.
- 그렇지 않은 경우에는 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
- 각 부분 리스트를 다시 재귀적으로 정렬한다.
- 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.
구현 과정
합병 정렬은 다음의 단계들로 이루어 진다.
- 분할(Divide): 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다.
- 정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 재귀 호출을 이용하여 다시 분할 단계를 적용한다.
- 결합(Combine): 정렬된 부분 배열들을 결합한다.
합병 정렬의 가장 중요한 점은 리스트의 모든 값을 비교하지 않는다는 것이다. 부분적인 리스트는 각각 그들끼리 정렬되어 있으므로 왼쪽 리스트와 오른쪽 리스트의 첫번째 값들은 각각의 리스트에서 가장 작은 원소임이 자명하다.
따라서 모든 값을 비교하지 않고 각 인덱스가 가리키는 리스트의 가장 왼쪽 원소끼리만 비교하면 된다.
- 왼쪽 리스트 원소 10이 오른쪽 리스트 원소 13보다 작으므로 10을 sorted에 넣고 왼쪽 리스트의 index를 증가시킨다.
- 왼쪽 리스트 원소 12이 오른쪽 리스트 원소 13보다 작으므로 12를 sorted에 넣고 왼쪽 리스트의 index를 증가시킨다.
- 왼쪽 리스트 원소 20이 오른쪽 리스트 원소 13보다 크므로 13을 sorted에 넣고 오른쪽 리스트의 index를 증가시킨다
- 왼쪽 리스트 원소 20이 오른쪽 리스트 원소 15보다 크므로 15을 sorted에 넣고 오른쪽 리스트의 index를 증가시킨다
- 왼쪽 리스트 원소 20이 오른쪽 리스트 원소 22보다 작으므로 20를 sorted에 넣고 왼쪽 리스트의 index를 증가시킨다.
- 왼쪽 리스트 원소 21이 오른쪽 리스트 원소 22보다 작으므로 21를 sorted에 넣고 왼쪽 리스트의 index를 증가시킨다.
- 왼쪽 리스트가 비었으므로 오른쪽 리스트의 22,25를 sorted에 넣는다
분할하는 과정에서의 시간 복잡도 O(N)
배열이 1, 2, 4, 8 ... 2^k로 분할되며 함수가 호출된다.
따라서 1 + 2 + 4 + ... + 2^k = 2N - 1 = O(N)의 시간 복잡도가 발생한다.
합병하는 과정에서의 시간 복잡도 O(Nlog2N)
첫번째 합병: 전부 리스트를 길이가 1인 리스트이므로 총 1개짜리 리스트가 N개 있다. (1 * N = N)
두번째 합병: 전부 리스트의 길이가 2인 리스트이므로 총 2개짜리 리스트가 N/2개 있다.(2 * N/2 = N)
세번째 합병: 전부 리스트의 길이가 4인 리스트이므로 총 4개짜리 리스트가 N/4개 있다.(4 * N/4 = N)
...
N번째 합병: 길이가 N인 하나의 리스트로 최종 합병한다. (N * 1 = N)
각 줄마다 N번의 비교 연산이 필요하고 모든 줄은 log2N개가 존재하므로
총 O(Nlog2N)번의 연산이 필요하다.
합병 정렬 알고리즘의 특징
장점
- 데이터 분포의 영향을 받지 않는다. 입력 데이터가 약간 정렬되어 있든 무작위든 상관 없이 정렬되는 시간이 동일하다. O(Nlog2N)
- 만약 레코드를 연결 리스트(Linked-List)로 구성한다면 링크 인덱스만 변경하면 되므로 데이터 이동은 무시할 수 있을 정도로 작아진다. 제자리 정렬(In-place sorting)으로 구현할 수 있다.
따라서 크기가 큰 레코드를 정렬할 경우 연결 리스트를 사용한다면 합병 정렬은 퀵 정렬을 포함한 어떤 정렬 방법보다 효율적이다.
단점
단점은 레코드를 임시 배열(Array)로 구현했을 때 발생한다.
- 레코드를 임시 배열로 구현하면 임시 배열만큼의 추가 공간이 필요하므로 제자리 정렬(In-place sorting)이 아니다.
- 레코드를 임시 배열로 구현하면 크기가 큰 경우 매우 큰 이동 횟수가 발생한다.
#include <bits/stdc++.h>
using namespace std;
vector<int> arr = { -1,5,7,1,3,3,2,9,8 };
vector<int> sorted(arr.size());
void merge(int start, int end)
{
int mid = (start + end) / 2;
int i = start;
int j = mid + 1;
int k = start;
while (i <= mid && j <= end)
{
if (arr[i] <= arr[j])
{
sorted[k++] = arr[i++];
}
else
{
sorted[k++] = arr[j++];
}
}
while (i <= mid)
{
sorted[k++] = arr[i++];
}
while (j <= end)
{
sorted[k++] = arr[j++];
}
for (int i = start; i <= end; i++)
{
arr[i] = sorted[i];
}
}
void merge_sort(int start, int end)
{
if (start < end)
{
int mid = (start + end) / 2;
merge_sort(start, mid);
merge_sort(mid + 1, end);
merge(start, end);
}
}
int main()
{
merge_sort(0, arr.size() - 1);
for (size_t i = 0; i < arr.size(); ++i)
{
cout << arr[i] << ' ';
}
return 0;
}