N24060 - 알고리즘 수업 - 병합 정렬 1

다음은 일반적인 병합 정렬 알고리즘이다.

import java.io.IOException;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    private static final BufferedReader BR = new BufferedReader(new InputStreamReader(System.in));
    private static final ArrayList<Integer> LOG = new ArrayList<>();
    private static StringTokenizer st;
    private static int[] arr;
    static int n;
    static int k;

    public static void main(String[] args) throws IOException{
        input();
        mergeSort(1, n);
        if(LOG.size() >= k) System.out.println(LOG.get(k-1));
        else System.out.println(-1);
    }

    private static void input() throws IOException {
        int i = 1;
        st = new StringTokenizer(BR.readLine());
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        arr = new int[n+1];
        st = new StringTokenizer(BR.readLine());
        while(st.hasMoreTokens())
            arr[i++] = Integer.parseInt(st.nextToken());
    }

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

    private static void merge(int l, int m, int r) {
        int[] tmp = new int[r-l+2];
        int i=l, j=m+1, t=1;
        while(i<=m && j<=r) {
            if(arr[i] < arr[j]) tmp[t++] = arr[i++];
            else tmp[t++] = arr[j++];
        }
        while(i <= m) tmp[t++] = arr[i++];
        while(j <= r) tmp[t++] = arr[j++];
        t = 1;
        for(i = l; i<=r;) {
            LOG.add(tmp[t]);
            arr[i++] = tmp[t++];
        }
    }
}

 

추후에 External Merge Sort Algorithm을 활용한 풀이를 추가하겠다.