[코테 알고리즘] 병합(Merge) 정렬

분할정복 알고리즘인 병합(Merge) 정렬

---

일단 반으로 계속 나누고 나중에 합치면서 정렬하자
이미 정렬이 되어있는 상태에서 새롭게 정렬된 상태를 만드는 것이다.

🕑 시간복잡도: O(N * log(2)N)
[ 반절씩 나누니까 너비가 N이면 높이는 log(2)N이다. ]
[ 높이만큼 내려가면 전체 너비만큼의 숫자를 정렬할 수 있다. ]

병합(Merge) 정렬 코드 구현

---

<백준 알고리즘, 2751번>

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

class Main {
    static int[] A;
    static int[] sorted;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        A = new int[N];
        sorted = new int[N];
        for(int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(br.readLine());
        }
        mergeSort(0, N-1);
        for(int i = 0; i < N; i++) {
            bw.write(A[i] + "\n");
        }
        bw.flush();
        bw.close();
    }

    private static void mergeSort(int m, int n) {
        if(m < n) {
            int middle = (m+n)/2;
            mergeSort(m, middle);
            mergeSort(middle+1, n);
            merge(m, middle, n);
        }
    }

    private static void merge(int m, int middle, int n) {
        int i = m;
        int j = middle + 1;
        int k = m;

        while(i <= middle && j <= n) {
            if(A[i] <= A[j]) {
                sorted[k] = A[i];
                i++;
            } else {
                sorted[k] = A[j];
                j++;
            }
            k++;
        }
        if(i > middle) {
            for(int t = j; t <= n; t++) {
                sorted[k] = A[t];
                k++;
            }
        } else {
            for(int t = i; t <= middle; t++) {
                sorted[k] = A[t];
                k++;
            }
        }
        for(int t = m; t <= n; t++) {
          A[t] = sorted[t];
        }
    }
}