https://www.acmicpc.net/problem/2751

Merge Sort

: 하나의 리스트를 두개의 균등한 크기의 리스트로 분할하고 각각 정렬한 후 합치는 정렬방법이다.

Merge Sort 방법

1. 분할 (Divide) : 리스트를 2개의 균등한 크기의 리스트(부분리스트)로 나누는 과정
2. 정복 (Conquer) : 부분 리스트를 정렬한다.
3. 결합 (Combine) : 정렬된 2개의 부분리스트를 하나의 리스트로 합병한다.

Merge Sort 코드

1. 분할

int mid = (start+end)/2; // 리스트의 가운데 인덱스
mergesort(start, mid); // start~mid까지 분할
mergesort(mid+1, end); // mid+1~end까지 분할

2. 정복

int front = start;
int back = mid+1;
int index = front;

// front나 back이 하나라도 유효 범위에 있다면
while(front<=mid || back<=end){ 
   
	// back이 범위를 넘었거나, 
	// front가 범위 안에 있으면서 arr[front]< arr[back] 이라면
	if(back>end || (front<=mid && arr[front]<arr[back])){
		temp[index++] = arr[front++];
	}else{ // 그 외의 경우
		temp[index++] = arr[back++];
	}
}

3. 결합

for(int i=start; i<=end; i++){
	arr[i]=temp[i];
}

전체코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

public class Boj_2751 {

    static int[] arr;
    static int[] temp;
    static int N;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());
        arr = new int[N];
        temp = new int[N];

        for(int n=0; n<N; n++){
            arr[n]=Integer.parseInt(br.readLine());
        }

        // sorting
        mergesort(0, N-1);

        // print
        for(int n=0; n<N; n++){
            bw.write(arr[n]+"\n");
        }

        bw.flush();

    }

    public static void mergesort(int start, int end){
        if(start<end){
            int mid = (start+end)/2;
            mergesort(start, mid);
            mergesort(mid+1, end);

            int front = start;
            int back = mid+1;
            int index = front;

            while(front<=mid || back<=end){ 
                if(back>end || (front<=mid && arr[front]<arr[back])){
                    temp[index++] = arr[front++];
                }else{
                    temp[index++] = arr[back++];
                }
            }

            for(int i=start; i<=end; i++){
                arr[i]=temp[i];
            }
        }
    }
}

시간 복잡도

Best : $O(Nlog2N)$
Worst : $O(Nlog2N)$
Avg : $O(Nlog2N)$