합병 정렬(Merge sort)

박경린·2021년 4월 18일
0

정렬

목록 보기
5/9

목차

  1. 합병 정렬이란?
  2. 사용 예시
  3. 코드
  4. 장점과 단점

1. 합병 정렬이란?

비교 기반 정렬 알고리즘입니다.
앞서 살펴 보았던 분할 정복 알고리즘을 이용한 정렬입니다.
분할, 정렬, 합병의 과정을 거칩니다.
여기서 정렬은 합병 정렬을 의미합니다.
그 말은 분할, (분할, 정렬, 합병), 합병 과 같이 제귀적과정을 거친다는 의미입니다.

2. 사용 예시


위 배열을 오름차순으로 배열해보겠습니다.

전체적인 과정은 아래와 같이 일어납니다.

앞서 설명드린 대로 분할, 정렬, 합병의 과정을 거처 합병 정렬이 이뤄지게 됩니다.

위 그림에서 파랜색은 정렬이 진행되지 않은 원소, 주황색은 정렬이 진행된 원소 입니다.
위 파란색이 분할 과정이고 주황색이 합병 과정입니다. 즉

이 부분 전체가 정렬 과정이라는 의미입니다.
이런 식으로 분할할 수 없을 때까지 분할한 뒤 다시 정렬하는 과정을 거치는 것이 전체적인 알고리즘의 과정입니다.

가장 작은 단위로 정렬이 끝나고 본격적으로 합병 과정으로 전환되는 부분입니다.
분할된 배열의 크기가 1일 경우 그 배열은 정렬된 것으로 합니다.
정렬된 배열들은 단순히 붙이는 것이 아닌 각 배열의 앞에서부터 작은 원소를 새로운 배열에 추가하는 방식을 사용합니다.

3. 코드

void mergeSort(int[] A, int low, int high, int[] B){
    if(low >= high) return;

    int mid = (low + high) / 2;

    mergeSort(A, low, mid, B);
    mergeSort(A, mid+1, high, B);

    int i=low, j=mid+1, k=low;
    for(;k<=high;++k){
        if(j > high ) B[k] = A[i++];
        else if(i > mid) B[k] = A[j++];
        else if(A[i] <= A[j]) B[k] = A[i++];
        else B[k] = A[j++];
    }

    for(i=low;i<=high;++i) A[i] = B[i];
}

4. 장점과 단점

4-1. 장점

퀵정렬과 같이 시간 복잡도에서 두각을 보입니다. 심지어 이 알고리즘의 경우에는 최악의 경우에도 O(N * log(N))으로 퀵정렬보다도 안정성있다고 말할 수 있습니다.

4-2. 단점

구현 난이도가 어렵습니다.

profile
개발자 취준생 입니다.

0개의 댓글