백준 2751번 수 정렬하기 2

package test;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;

public class Q20p128 {

public static void main(String[] args) throws NumberFormatException, IOException {
	// TODO Auto-generated method stub
	BufferedReader buf =new BufferedReader(new InputStreamReader(System.in));
	int len =(Integer.parseInt(buf.readLine()));
	int[] arr = new int[len];
	Scanner sc = new Scanner(System.in);
	for(int i=0;i<len;i++)
		arr[i]=sc.nextInt();
	
	mergeSort(arr);
	for(int i=0;i<len;i++)
		System.out.println(arr[i]);
	
	buf.close();
}
public static void mergeSort(int []arr){
	int[] temp=new int[arr.length];
	mergeSort(arr,temp,0,arr.length-1);
}

public static void mergeSort(int []arr, int[] temp, int start, int end){
	if(start<end) {
		int mid =(start+end)/2;
		mergeSort(arr,temp,start,mid);
		mergeSort(arr,temp,mid+1,end);
		merge(arr,temp,start,mid,end);
	}
}
public static void merge(int[] arr, int[] temp, int start,int mid, int end) {
	for(int i=0;i<arr.length;i++)
		temp[i]=arr[i];
	int part1=start;
	int part2=mid+1;
	int index= start;
	
	while(part1<=mid && part2<=end) {
		if(temp[part1]<=temp[part2]) {
			arr[index]=temp[part1];
			part1++;
		}
		else {
			arr[index]=temp[part2];
			part2++;
		}
		index++;
		
        //앞 파트가 남아있을 경우를 위하여, 뒤에는 남아도 그대로 넣어도 가능해서 상관없다.
		for(int i=0;i<=mid-part1;i++) {
			arr[index+i]=temp[part1+i];
		}
	

	}
}

}