Merge Sort

public class mergesort {

	static int[] b;
	public static void main(String[] args) {\
		int[] arr = new int[] {7, 6, 5, 8, 3, 2, 9, 1};
		int n = arr.length;
		
		mergeSort(arr, 0, n-1);
		
		for(int i = 0; i < n; i++) {
			System.out.print(arr[i]);
		}
		
	}
	public static void mergeSort(int[] a, int start, int end) {
		if(start < end) {
			int mid = (start + end)/2;
			mergeSort(a, start, mid );
			mergeSort(a, mid+1, end);
			merge(a, start, mid, end);
			
		}
	}
	public static void merge(int[] a, int m, int mid, int n) {
		int i = m;
		int j = mid + 1;
		int k = m;
		b = new int[a.length];
		while( i <= mid && j <= n) {
			if( a[i] <= a[j]) {
				b[k] = a[i];
				i++;
			}else {
				b[k] = a[j];
				j++;
			}
			k++;
		}
		
		if( i > mid) {
			for(int x = j; x <= n; x++) {
				b[k] = a[x];
				k++;
			}
		}else {
			for(int x = i; x<=mid;x++) {
				b[k] = a[x];
				k++;
			}
		}
		
		for(int x = m; x <= n; x++) {
			a[x] = b[x]; 
		}
	}
}

머지소트는 퀵소트 보단 더 직관적으로 안다가온다.

우선 각각의 배열의 성분을 하나가 될때까지 계속 쪼갠다. 중간의 사이즈로
한개가 될때까지 쪼개주기.
탈출 조건은 끝 에 값이 시작값 보다 작아질때까지.

그리고 이제 다 쪼개지면, 정렬을 하게되는데 정렬은 쉬움
정렬을 할때 팁은, 데이터를 담아두는 정렬을 스태틱으로 쓴다음에 계속 해서 재사용하면,
메모리값을 절약할 수 있음.

데이터 다 담아둔다음에, 이제 a값에 복사해줌. 어차피 a값은 우리가 찾고자 하는 arr값과
주소값을 동일하게 물고있어서 재귀적으로 돌아도 변경되게 되어있음.