1. 문제 설명

주어진 정수 리스트를 오름차순으로 정렬하는 문제입니다. 이 문제는
병합 정렬(Merge Sort) 알고리즘을 사용하여 해결합니다.
병합 정렬은 분할 정복(divide and conquer) 알고리즘의 일종으로, 주어진 리스트를
재귀적으로 두 개의 서브 리스트로 나눈 뒤, 이들을 각각 정렬하고 다시 하나의 리스트로
병합하는 방식입니다.

2. 문제 입력

– 첫 번째 입력은 정렬할 정수의 개수 N (1 ≤ N ≤ 106)입니다.
– 두 번째 입력으로는 N개의 정수가 주어집니다. 이 정수들은 임의의 음수 및
양수를 포함할 수 있으며, 각 정수는 32비트 정수의 범위에 있습니다.

3. 문제 출력

정렬된 정수 리스트를 한 줄에 공백으로 구분하여 출력합니다.

4. 알고리즘 설명

병합 정렬의 주요 아이디어는 배열을 중간에서 두 부분으로 나누고, 각각의 부분을 재귀적으로 정렬한 다음,
정렬된 두 부분을 병합하여 최종적으로 정렬된 배열을 만드는 것입니다.

4.1 알고리즘 단계

  1. 배열의 크기가 1 이하일 경우, 이미 정렬되어 있으므로 해당 배열을 반환합니다.
  2. 배열을 중간 인덱스를 기준으로 두 개의 부분 배열로 나눕니다.
  3. 각 부분 배열에 대해 재귀적으로 병합 정렬을 호출합니다.
  4. 정렬이 완료된 두 부분 배열을 병합하여 하나의 정렬된 배열로 만듭니다.

5. 코드 구현


#include <iostream>
#include <vector>

using namespace std;

// 배열을 병합하는 함수
void merge(vector &arr, int left, int mid, int right) {
    int n1 = mid - left + 1; // 왼쪽 배열 크기
    int n2 = right - mid;    // 오른쪽 배열 크기
    vector L(n1), R(n2); // 서브 배열 생성

    // 서브 배열에 값 저장
    for (int i = 0; i < n1; ++i)
        L[i] = arr[left + i];
    for (int j = 0; j < n2; ++j)
        R[j] = arr[mid + 1 + j];

    // 서브 배열 병합
    int i = 0; // 인덱스 i는 L
    int j = 0; // 인덱스 j는 R
    int k = left; // 인덱스 k는 arr

    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    // 남은 요소들 처리
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

// 병합 정렬 함수
void mergeSort(vector &arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2; // 중간점 계산

        mergeSort(arr, left, mid); // 왼쪽 배열 정렬
        mergeSort(arr, mid + 1, right); // 오른쪽 배열 정렬

        merge(arr, left, mid, right); // 두 배열 병합
    }
}

int main() {
    int N;
    cin >> N; // 정수 개수 입력
    vector arr(N);

    for (int i = 0; i < N; i++) {
        cin >> arr[i]; // 정수 리스트 입력
    }

    mergeSort(arr, 0, N - 1); // 병합 정렬 호출

    // 결과 출력
    for (int i = 0; i < N; i++) {
        cout << arr[i];
        if (i < N - 1) cout << " "; // 공백 구분
    }
    cout << endl;

    return 0;
}

6. 복잡도 분석

병합 정렬의 시간 복잡도는 O(N log N)입니다. 여기서 N은 배열의 크기입니다.
이는 배열이 두 번으로 나누어지기 때문에 log N의 깊이를 가지며,
각 단계에서 합치는 데 N의 시간이 소요되기 때문입니다.
따라서 병합 정렬은 평균적인 경우와 최악의 경우 모두 O(N log N)의 성능을 보장합니다.

공간 복잡도는 사용된 추가적인 메모리와 관련이 있으며,
병합 정렬에서는 두 개의 서브 배열을 생성하므로 O(N)의 추가 메모리를 필요로 합니다.

7. 결론

병합 정렬 알고리즘은 안정적(stable)이며, 대량의 데이터를 정렬하는 데 효과적입니다.
다양한 프로그래밍 과제 및 문제 해결에서 활용될 수 있습니다.
초고속의 정렬 알고리즘이 필요한 경우(예: Quick Sort)와는 달리,
병합 정렬은 일관된 성능과 간단한 구현을 특징으로 하여 많은 상황에서 사랑받고 있습니다.

8. 추가 연습 문제

아래의 문제를 풀어보세요.

  1. 주어진 리스트에서 최빈값을 찾는 프로그램을 작성하세요.
  2. 병합 정렬을 응용하여 두 개의 정렬된 배열을 하나의 정렬된 배열로 병합하는 프로그램을 작성하세요.