병합정렬

병합정렬

참고:https://www.youtube.com/watch?v=QAyl79dCO_k

public class Main {

    static int[] arr = {3,9,4,7,5,0,1,6,8,2};

    public static void main(String[] args){

        print(arr);

        int[] temp = new int[arr.length];
        meargeSort(arr, temp, 0, arr.length-1);
        print(arr);


    }

    static void meargeSort(int[] arr, int[] temp, int start, int end){

        if(start<end){
            int mid = (start+end)/2;
            meargeSort(arr, temp, start, mid);
            meargeSort(arr, temp, mid+1, end);
            merge(arr, temp, start, mid, end);
        }
    }

    static void merge(int[] arr, int[] temp, int start, int mid, int end){

        for(int i=start; i<=end; i++){
            temp[i] = arr[i];
        }

        int part1 = start;
        int part2 = mid+1;
        int index = start;

        //두 파트 모두 남아있을때만(한쪽이라도 먼저 끝나면 종결된다)
        while(part1 <= mid && part2 <= end){

            if(temp[part1] <= temp[part2]){
                arr[index] = temp[part1];
                part1++;
            }else{
                arr[index] = temp[part2];
                part2++;
            }
            index++;
        }

        //앞쪽이 남았을 경우. (뒷쪽은 어자피 복사되어 있으니 그대로 두면 된다)
        for(int i=0; i<=mid-part1; i++){
            arr[index+i] = temp[part1+i];
        }
    }


    static void print(int[] arr){
        for(int a: arr){
            System.out.printf("%d ", a);
        }
        System.out.println();
    }
}