algorithm 병합정렬

재귀호출 방식의 병합정렬

public class Main {
	public static void main(String[] args) {
		int[] a = {31, 41, 6, 26, 41, 58, 99, 85, 59};
		for(int out : a) {
			System.out.print(out + " ");
		}
		System.out.println();

		mergeSort(a, 0, a.length-1);

		for(int out : a) {
			System.out.print(out + " ");
		}
		System.out.println();
	}
	
	private static void mergeSort(int[] a, int p, int n) {
		int q = 0;
		if (p < n) {
			q = (p + n) / 2;
			mergeSort(a, p, q);
			mergeSort(a, q+1, n);
			merge(a, p, q, n);
		}
	}
	
	private static int[] merge(int[] a, int p, int q, int n) {
		int i = p, j = q+1;
		int[] result = new int[n-p+1];
		for(int k = 0; k < n-p+1; k++) {
			if(i <= q && j <= n) {
				if(a[i] <= a[j]) {
					result[k] = a[i];
					i++;
				} else {
					result[k] = a[j];
					j++;
				}
			} else if(i > q) {
				result[k] = a[j];
				j++;
			} else if(j > n) {
				result[k] = a[i];
				i++;
			}
		}
		for(int k = 0; k < result.length; k++) {
			a[p+k] = result[k];
		}
		return a;
	}
}