Merge Sort

import java.util.Scanner;

public class Main2 {	
	
	static int n;
	static int[] arr = {2,1,3,-1};
	static int[] temp = new int[1000005];
	
	static public void merge_sort(int st,int ed) {
		// 배열의 길이가 2라고 가정하면 st=0, ed=2
		// 배열의 길이가 3일때 홀수일때도 체크해보면 문제없음
		if(ed == st+1) return;
		int mid = (st+ed)/2;
		merge_sort(st,mid); // (0,1)
		merge_sort(mid,ed); // (1,2)
		merge(st,ed); // (0,2)
	}
	
	static public void merge(int st,int ed) {
		// 정렬된 두 리스트를 하나의 정렬된 리스트로 합치는 과정
		// A = [1,2]
		// B = [3,4]
		int mid = (st+ed)/2;
		int lIndex = st;
		int rIndex = mid;		
		for(int i=st;i<ed;i++) {
			// 2가지 경우 
			// 1.왼쪽 또는 오른쪽 리스트를 새로운 리스트로 다 옮긴 경우
			// 2.왼쪽과 오른쪽 리스트에 있는 값을 비교하면서 더 작은 값을 새로운 리스트로 옮긴다(오름차순 기준)
			
			// 여기서 주의할점은 2번을 먼저 체크하고 1번을 체크하는 식으로 순서를 변경하면 index의 값을 넘어서는 런타임 에러가 발생하거나 정렬하는 순서가 뒤엉킴			
			// 예를 들어서 오른쪽 리스트에 있는 값이 모두 새로운 리스트로 먼저 넘어가고 왼쪽과 오른쪽 리스트를 비교시 오른쪽 리스트에 있는 인덱스가 범위를 넘어서기 떄문에 문제 발생
			// 왼쪽으로 리스트가 먼저 넘어가면 왼쪽 리스트의 인덱스는 오른쪽 리스트의 인덱스를 사용하므로 문제발생 
			if(lIndex == mid) temp[i] = arr[rIndex++];
			else if(rIndex == ed) temp[i] = arr[lIndex++];			
			else if(arr[lIndex] <= arr[rIndex]) temp[i] = arr[lIndex++];
			else temp[i] = arr[rIndex++];
		}
		for(int i=st;i<ed;i++) arr[i] = temp[i];
	}
	
	
	public static void main(String[] args) {		
		n = 4;		
		merge_sort(0, n);				
		for(int i=0;i<n;i++) {
			System.out.print(arr[i] + " ");
		}
	}

}