재귀함수를 이용한 병합정렬 구현

병합정렬이란

배열을 가장 작은데이터 집합으로 분할하고 서로 인접한 집합끼리 순차적으로 병합해 나가면서 전체 배열을 정렬한다.

구현순서

1. 주어진 배열을 절반씩 나누는 과정을 반복하여 가장작은 데이터 집합으로 분할한다

•  배열에 들어있는 값이 8개면 8개의 집합으로 분할

2. 인접한 두개의 집합에 각각 포인터를 두어 현재 두 집합의 포인터가 가리키는 값을 비교하고,
   오름차순인 경우에는 더 작은 값을 임시배열에 저장하고 더 작은 값을 가진 집합의 포인터를 한칸 이동한다.

•  내림차순인 경우에는 반대

3. 위의 과정을 반복하여 임시배열에 두 집합이 정렬되었으면
   원본배열의 두 집합에 해당하는 인덱스 부분에 임시배열을 저장한다.

구현시 어려웠던점

StackOverFlow Error - 인덱스의 중간지점을 잘못찾아 해당오류 발생

재귀함수 사용시 잘못된 인자값으로 인해 너무많은 함수가 반복실행되어 발생하는 오류

인덱스의 중간지점 찾기

시작인덱스 + (마지막인덱스 - 시작인덱스) / 2

구현코드

public class Q21 {

	public static void main(String[] args) throws Exception{
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(in.readLine());
		
		int[] arr = new int[n];
		StringTokenizer st = new StringTokenizer(in.readLine());
		for(int i=0; i<n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		sort(arr, 0, n-1);
		
		for(int i= 0; i<n; i++) {
			System.out.println(arr[i]);
		}
		
	}
	
	public static void sort(int[] arr, int s, int e) {
		if(e-s>=1) {
			int m= s+(e-s)/2;
			sort(arr, s, m);
			sort(arr,m+1, e);
			
			int point1 = s;
			int point2 = m+1;
			int[] tmp = new int[e+1];
			int index = 0;
			while(point1 <= m && point2 <= e) {
				if(arr[point1]>arr[point2]) {
					tmp[index] = arr[point2];
					index++; point2 ++;
				}else {
					tmp[index] = arr[point1];
					index++; point2++;
				}
			}
			if(point1<=m) {
				while(point1 <= m) {
					tmp[index] = arr[point1];
					index++; point1++;
				}
			}
			if(point2<=e) {
				while(point2 <= e) {
				tmp[index] = arr[point2];
				index++; point2++;
				}
			}
			int j = 0;
			for(int i = s; i<=e; i++) {
				arr[i] = tmp[j];
				j++;
			}
		}
	}

}