[실전 문제] 합병정렬 구현하기

1. 문제

n개의 정수가 주어질 때, 이를 합병정렬을 이용하여 오름차순으로 정렬하는 프로그램을 작성하시오.

---

입력

첫 번째 줄에 n이 주어진다. ( 1 ≤ n ≤ 100,000 ) 두번째 줄에 n개의 정수가 주어진다. 

출력

첫 번째 줄에 n개의 숫자를 합병정렬을 이용하여 오름차순으로 정렬한 결과를 출력한다.

예제 입력

10
2 5 3 4 8 7 -1 9 10 2

예제 출력

-1 2 2 3 4 5 7 8 9 10

 

 

 

2. 풀이

합병 정렬은 반으로 나누어 정렬을 하는 고급 정렬이다. Arrays.sort를 이용하여 쉽게 정렬을 해도 좋으나, 합병 정렬을 정확히 숙지하기 위해 직접 구현을 해봐야한다.

import java.io.*;
import java.util.StringTokenizer;

public class Main {

    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    private static int n;
    private static int[] arr;
    private static int[] tmp;

    public static void main(String[] args) throws IOException {

        n = Integer.parseInt(br.readLine());

        arr = new int[n];
        tmp = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        mergeSort(0, n-1);

        for(int i = 0; i < n; i++) {
            bw.write(arr[i] + " ");
        }

        br.close();
        bw.flush();
        bw.close();
    }

    private static void mergeSort(int s, int e) {
        if(s >= e) return;
        int mid = (s+e)/2;

        mergeSort(s, mid);
        mergeSort(mid+1, e);
        merging(s, mid, mid+1, e);
    }

    private static void merging(int s1, int e1, int s2, int e2) {
        int p = s1;
        int q = s2;
        int tmpIdx = 0;

        while(p <= e1 && q <= e2) {
            if(arr[p] < arr[q]) tmp[tmpIdx++] = arr[p++];
            else tmp[tmpIdx++] = arr[q++];
        }

        if(p > e1) {
            for(int i = q; i <= e2; i++) {
                tmp[tmpIdx++] = arr[i];
            }
        } else {
            for(int i = p; i <= e1; i++) {
                tmp[tmpIdx++] = arr[i];
            }
        }

        for(int i = s1; i <= e2; i++) {
            arr[i] = tmp[i - s1];
        }
    }

}