[알고리즘] 합병정렬/병합정렬 (Merge Sort) Java Example

 

합병정렬 알고리즘

합병정렬(Merge Sort) 알고리즘은 원소를 반으로 분할한 후 분할한 원소를 다시 병합하는 정렬 방법입니다.

초기 세팅 변수 left = 0 , rigth = 배열 길이-1 , mid = (left+right)/2

• 원소를 반으로 계속 나눈다 >>> 배열(리스트)의 길이가 1이 될 때 까지 분할합니다. (mergeSortDevide)
• 1개씩 분할된 원소들을 정렬하면서 합친다. (Merge)

 

public class Merge_Sort {
 
    public static void main(String[] args) {
        
        int[] arr = { 10, 80, 91, 90, 70 };
        
        /*원소를 반으로 나누는 함수*/
        mergeSortDevide(arr, 0, arr.length - 1);
        
        /*합병 정렬된 배열을 출력하는 함수*/
        output_merge_arr(arr); 
    }
 
    private static void mergeSortDevide(int[] arr, int left, int right) {
        
        /*원소의 수가 2개 이상일경우 실행*/
        if (left < right) { 
            
            /*반으로 나누기 위한 변수*/
            int mid = (left + right) / 2; 
            
            /*앞(왼쪽)부분 재귀 호출*/
            mergeSortDevide(arr, left, mid); 
        
            /*뒤(오른쪽)부분 재귀 호출*/
            mergeSortDevide(arr, mid + 1, right);
            
            /*원소를 Merge하는 함수*/
            merge(arr, left, mid, right); 
        }
    }
 
    private static void merge(int[] arr, int left, int mid, int right) {
 
        int i = left;
        int j = mid + 1;
        int temp_index = left;
 
        int[] temp = new int[arr.length];
 
        while (i <= mid && j <= right) {
            if (arr[i] < arr[j]) {
                temp[temp_index++] = arr[i++];
            } else {
                temp[temp_index++] = arr[j++];
            }
        }
        
        /*앞(왼쪽)부분 배열에 원소가 남아있는 경우*/
        while (i <= mid) { 
            temp[temp_index++] = arr[i++];
        }
        
        /*뒤(오른쪽)부분 배열에 원소가 남아있는 경우*/
        while (j <= right) {
            temp[temp_index++] = arr[j++];
        }
 
        for (int index = left; index < temp_index; index++) {
            arr[index] = temp[index];
        }
    }
 
    private static void output_merge_arr(int[] arr) {
        
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
 
}