[Practice] 합병 정렬

문제

주어진 배열을 바탕으로 합병 정렬(분할 정복의 한 종류)

풀이

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

public class Main {
	
	static void rMergeSort(int[] arr, int left, int right) {
		if(left<right) {
			int m = (left+right)/2;
			rMergeSort(arr,left,m);
			rMergeSort(arr,m+1,right);
			merge(arr,left,m,right);
		}
		
	}
	static void merge(int[] arr, int left, int m, int right) {
		int i=left, k = left;
		int j=m+1;
		int[] tmp = new int[100];
		while(i<=m && j<=right) {
			if(arr[i]<arr[j])
				tmp[k++] = arr[i++];
			else
				tmp[k++] = arr[j++];
		}
		while(i<=m)
			tmp[k++] = arr[i++];
		while(j<=right)
			tmp[k++] = arr[j++];
		
		for(int idx=left;idx<=right;idx++)
			arr[idx] = tmp[idx];
	}
	public static void main(String[] args) throws IOException {
        //선언 및 입력
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st;
    	StringBuilder sb = new StringBuilder();
    	int[] arr = {100,2,4,200,300,543,11};
    	//계산
    	rMergeSort(arr,0,arr.length-1);
    	for(int i=0;i<arr.length;i++)
    		System.out.print(arr[i]+" ");
	}
}