병합 정렬

분할 정복 기법을 사용하는 정렬

1. 병합 정렬 ( Merge Sort )

 

출처 : https://commons.wikimedia.org/

public class MergeSort {
    static int[] tempArr;
    static void sort(int[] arr, int left, int right){
        if(left<right){ // 원소가 2개 이상일 경우 계속 분할
            int mid = (left+right)/2;
            sort(arr, left, mid);
            sort(arr, mid+1, right);

            //투포인터 사용하여 정렬 시작
            int lp = left;
            int rp = mid+1;
            int idx = left; // 정렬하며 값을 넣어줄 인덱스

            // Normal case : 양쪽 배열을 비교하면서 정렬-병합
            while(lp<=mid && rp<=right){
                tempArr[idx++] = arr[lp] < arr[rp] ? arr[lp++] : arr[rp++];
            }
            // Special case : 한쪽이 비어있을경우 나머지 몰아주기
            if(lp > mid){ // 왼쪽 배열을 다 썻을경우
                while(rp<=right){
                    tempArr[idx++] = arr[rp++];
                }
            }
            if(rp>right){ // 오른쪽 배열을 다 썼을경우
                while(lp<=mid){
                    tempArr[idx++] = arr[lp++];
                }
            }
            for(int i=left; i<=right; i++){
                arr[i] = tempArr[i];
            }
        }
    }
}
public class SortTest {
    public static void main(String[] args) {
        int[] arr = AlgoritmUtil.makeRandomIntArray(1, 10, 10);
        System.out.println("========== MERGE ==========");
        System.out.println("BEFORE : "+Arrays.toString(arr));
        MergeSort.tempArr = new int[arr.length];
        MergeSort.sort(arr, 0 ,arr.length-1);
        System.out.println("AFTER : "+Arrays.toString(arr));
    }
}
//BEFORE : [5, 8, 9, 3, 8, 9, 10, 3, 6, 4]
//AFTER : [3, 3, 4, 5, 6, 8, 8, 9, 9, 10]