[Week1] 병합 정렬 (MergeSort)

병합 정렬 (Merge Sort)

 

정의

합병 정렬이라고도 부르며, 분할 정복 방법을 통해 구현

 

※ 분할 정복 (divide and conquer)
   문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략

 



빠른 정렬로 분류되며, 퀵 정렬과 함께 많이 언급되는 정렬 방식이다. 

안정 정렬에 속한다. 

 

퀵 정렬과의 차이점
퀵 정렬 : 우선 피벗을 통해 정렬 (partition) → 영역을 쪼갬(quickSort)
병합 정렬 : 영역을 쪼갤 수 있을 만큼 쪼갬(mergeSort) → 정렬(merge)

 

Process

static void mergeSort(int[] array, int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        mergeSort(array, left, mid);
        mergeSort(array, mid + 1, right);

        merge(array, left, mid, right);
    }
}

 

요소를 쪼갠 후, 정렬

 

 

이미 합병의 대상이 되는 두 영역이 각 영역에 대해서 정렬이 되어있기 때문에 단순히 두 배열을 순차적으로 비교하면서 정렬할 수 있다. 

정렬 과정에서 한 배열이 모두 소진되었으면 나머지는 그대로 배열에 넣어줌

 

합병 정렬은 순차적인 비교로 정렬을 진행하므로 LinkedList의 정렬이 필요할 때 사용하면 효율적이다. 
(퀵 정렬은 임의 접근이기 때문에 비효율적임)

 

 

시간복잡도

평균	최선	최악
Θ(nlogn)	Ω(nlogn)	O(nlogn)