알고리즘 - 병합정렬

- 자바코드로 구현한 병합정렬

package day0322_분할정복;

import java.util.Arrays;

public class 병합정렬 {

	static int[] arr;
	static int[] result;
	public static void main(String[] args) {
		arr = new int[] {3, 1, 4, 6, 9, 2, 8, 7, 5};	
		result = new int[arr.length];
		sort(arr, 0, arr.length-1);
		System.out.println(Arrays.toString(result));
		}
		
	
	
	public static void sort(int[]arr, int left, int right) {
		if(left>=right) return;
		//분할과정
		sort(arr, left, (left+right)/2);
		sort(arr, (left+right)/2+1, right);
        
        //합치기
		merge(arr, left, right);
		
	}
	
	
	public static void merge(int[] arr, int left, int right) {
    	//가운데 값을 기준으로 왼쪽은 left포인터, 오른쪽은 right포인터를 보며 합쳐나갈 것.
		int m = (left+right)/2 ;
        //왼쪽 포인터
		int i = left;
        //오른쪽 포인터
		int j = m+1;
        //결과 값 배열의 index
		int idx = left;
        //왼쪽 포인터가 왼쪽배열 범위를, 오른쪽 포인터가 오른쪽 배열 범위를 벗어나지 않을 때 실행
		while(i<=m && j<=right) {
        //왼쪽이 작으면 왼쪽포인터가 가리키는 값을 결과에 넣고 포인터++
			if(arr[i]<=arr[j]) {
				result[idx++] = arr[i];
				i++;
          //오른쪽이 클 때는 반대로!
			}else {
				result[idx++] = arr[j];
				j++;
			}
			
		}
        //왼쪽 또는 오른쪽 배열의 숫자를 모두 털어내고 난 후!
        //아래 두개의 for문을 돌면, 둘 중에 비어있는 쪽의 for문만 동작
        //남아 있는 배열 털어내기!!
        
        //i가 m+1이 됐다면(다 털어냈다면) 해당 for문 동작x
		for(int k=i; k<m+1; k++) {
			result[idx++] = arr[k];
		}
		//오른쪽도 마찬가지
		for(int k=j; k<=right; k++) {
			result[idx++] = arr[k];
		}
		
        //결과값에 넣은 모든 배열을 다시 원래 배열에 넣기(정렬된 결과 넣기!)
		for(int k=left; k<=right; k++) {
			arr[k] = result[k];
		}
	}
}