[Sort] 합병 정렬

합병 정렬 - MergeSort

---

합병(병합) 정렬은 문제를 분할하고 분할한 문제를 다시 합치는 과정에서 정렬을 수행하는 알고리즘이며 분할 정복(Divide and Conquer) 알고리즘을 기반으로 두고 있다. 시간복잡도는 모든 상황에서 O(nlog(n))의 시간복잡도를 가진다. 합병 정렬은 문제 분할 후 데이터를 비교하면서 찾기 때문에 비교 정렬이며, 정렬의 대상이 되는 데이터 외에 추가적인 공간을 필요로 하기 때문에 제자리 정렬이 아니다.

https://commons.wikimedia.org/wiki/File:Merge_sort_algorithm_diagram.svg

 

 

예제코드

---

public class MergeSort {

    private static final Logger logger = Logger.getLogger(MergeSort.class.getName());

    private static int[] arr;
    private static int[] mergedArr;

    public static void main(String[] args) {
        arr = new int[]{5, 1, 3, 8, 4, 9, 2, 7};
        mergedArr = new int[arr.length];

        divide(0, arr.length-1);

        logger.info("mergedArr: " + Arrays.toString(mergedArr));
    }

    public static void divide(int left, int right) {
        if(left == right) return;

        int mid = (left+right)/2;

        divide(left, mid);
        divide(mid+1, right);

        conquer(left, mid, right);
    }

    public static void conquer(int left, int mid, int right) {
        int lIdx = left;
        int rIdx = mid+1;
        int mIdx = left;

        while(lIdx <= mid && rIdx <= right) {
            if(arr[lIdx] >= arr[rIdx]) mergedArr[mIdx++] = arr[rIdx++];
            else mergedArr[mIdx++] = arr[lIdx++];
        }

        while(rIdx <= right) {
            mergedArr[mIdx++] = arr[rIdx++];
        }
        while(lIdx <= mid) {
            mergedArr[mIdx++] = arr[lIdx++];
        }

        System.arraycopy(mergedArr, left, arr, left, right+1-left);
    }
}

 

 

Reference

---

자바 [JAVA] - 합병정렬 / 병합정렬 (Merge Sort)