JAVA 병합정렬 알고리즘

병합정렬 MergeSort  

-보통 데이터가 엄청 많을때 사용하는 방식

-쪼갠 후에 쪼개진 아이끼리 순서를 맞춰줘서 병합 후에 다시 맞추고 가는 방식

이해를 위한 동영상

1. 
   

1. 자바 코드

public class MergeSort {
    public static void main(String[] args) {
        //1. 입력 : 원본 데이터가 정렬되어있다고 가정, 오름차순
        int[] first = {1, 3, 5};
        int[] second = { 2, 4 };
        int[] mearge = new int[first.length + second.length]; // MEARGE될 배열
        int i = 0, j = 0, k = 0; //i : first 인덱스 , j : second 인덱스, k : mearge 인덱스
        int m = first.length;
        int n = second.length;     
       
        //2. 처리
        while(i < m && j < n){ 
            if(first[i] <= second[j]){
                mearge[k++] = first[i++];
            }else{
                mearge[k++] = second[j++];
            }
        }
       
        while(i<m){ 
            mearge[k++] = first[i++];
        }
       
        while(j<n){ 
            mearge[k++] = second[j++];
        }
       
        //3. 출력
        for(int p = 0; p< mearge.length; p++){
            System.out.print(mearge[p] + "  ");
        }
    }
}