[Sorting] 병합정렬

지난 포스팅(버블, 선택, 삽입 정렬)에 이어 오늘은 Merge Sort에 대해 알아보려고 한다. Merge Sort는 분할정복 알고리즘 중 하나로 최소 단위로 쪼개고 병합하는 과정에서 정렬이 이루어진다. Merge Sort의 시간복잡도의 경우 최악, 평균, 최선 모두 O(nlogn)의 시간복잡도를 가진다.

---

Merge Sort

병합정렬로 최소단위까지 나눈 후 다시 결합시키면서 정렬해 가는 알고리즘으로 Merge Sort는 분할정복 알고리즘을 사용한 정렬방법이다.

• Not In Place Sorting : 추가적인 메모리 공간이 필요하므로 제자리 정렬이 아니다.
• Stable Sorting : 중복된 데이터를 순서대로 정렬

Merge Sort 과정

정렬 과정

1. 데이터 집합을 N/2씩 최소 단위가 될 때까지 나눈다.(마지막 2개에서 1개로 나누는 과정은 Conquer 과정에서 진행됨 )
2. 분할된 데이터를 다시 담을 Array가 추가로 필요하므로 생성한다.
3. 2개의 배열을 두고 각 배열의 처음 인덱스부터 데이터 비교 연산을 통해 새로 할당된 배열에 순서대로 삽입한다.
4. 2개의 배열 중 하나의 배열을 모두 비웠다면 나머지 배열의 데이터를 새로 할당된 배열에 전부 순서대로 삽입한다.
5. 추가 Array에 담긴 정렬된 데이터는 기존 배열 리스트에 다시 복사한다.
6. 재귀함수를 통해 배열의 결합과정을 거치며 정렬을 마친다.

 

이 과정을 코드로 나타내면

import java.util.Scanner;

public class merge {

    static int N;                      // 입력할 데이터의 개수
    static int arr[];                  // 입력될 데이터 집합
    static int sortedArr[];            // 정복을 통해 삽입될 데이터 집합
    static int count = 0;              // 정복이 일어나는 횟수 계산

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        arr = new int[N];
        sortedArr = new int[N];

        for(int i = 0; i< N; i++)
            arr[i] = sc.nextInt();

        Divide(0, N-1);   //데이터 집합의 처음 인덱스와 마지막 인덱스 정보 제공

        for(int i : sortedArr)
            System.out.print(i + " ");

    }

    // 분할된 배열을 정복을 통해 합치는 함수
    static void merge(int left, int mid, int right) {
        count++;
        int i = left;
        int j = mid+1;
        int sortedIdx = left;

        // i 또는 j가 배열의 크기를 넘지 않도록 하는 조건문
        while(i <= mid && j <=right) {
            if(arr[i] < arr[j])
                sortedArr[sortedIdx++] = arr[i++];
            else
                sortedArr[sortedIdx++] = arr[j++];
        }

        // 오른쪽 배열의 데이터의 비교가 모두 끝난 경우 왼쪽 배열의 데이터 일괄 저장
        for(;i <= mid; i++ )
            sortedArr[sortedIdx++] = arr[i];
        // 왼쪽 배열의 데이터의 비교가 모두 끝난 경우 오른쪽 배열의 데이터 일괄 저장
        for(;j <= right; j++)
            sortedArr[sortedIdx++] = arr[j];

        for(int l = left; l<= right; l++)
            arr[l] = sortedArr[l];


        // 현재까지 정렬된 배열 프린트 count는 merge 함수의 호출 횟수(정복을 통해 결합되는 횟수)
        System.out.print("\ncount : " + count + "  ");
        for(int l = left; l<= right; l++)
            System.out.print(sortedArr[l] + " ");
        System.out.println();
        
    }

    // 데이터 집합을 최소 단위로 나누는 함수(매개변수는 배열의 처음과 끝 인덱스 정보 제공)
    static void Divide(int left, int right) {

        int mid;

        // 하나의 배열은 2개로 나누어진다.
        if(left < right) // 배열의 크기가 1인 경우에는 조건을 만족하지 않음.
        {
            mid = (left + right) /2;
            Divide(left, mid);
            Divide(mid+1, right);
            merge(left, mid, right);
        }

    }
}

 

 

 

시간복잡도

Merge Sort의 흐름

 

• Divide하는 과정에는 데이터들의 비교나 이동이 일어나지 않는다.
• Conquer하는 과정에서 1개의 데이터를 가지고 있는 8개의 배열은 합쳐져서 2개의 데이터를 지닌 4개의 배열, 4개의 데이터를 지닌 2개의 배열 8개의 데이터를 지닌 1개의 배열로 합쳐진다. n개의 데이터가 2^k개 있을 경우 k = log2^n이 된다.
• 각 정복 단계에서 데이터의 비교 연산은 최대 두 배열의 데이터 갯수 만큼 이뤄진다.
• ex) {1, 8}과 {2, 5}의 경우 1과 2의 비교, 2와 8, 5와 8 그리고 마지막 데이터의 삽입까지 4번의 비교 발생.
• 그리고 임시로 저장된 데이터를 원래 배열에 다시 저장하는데 n번의 비교연산이 필요하다.
• 따라서 정복 과정의 한 레벨에서 비교와 이동 연산은 2n번이 발생한다.
• 즉 kn = log 2^n x 2n으로 2nlog2^n 이다.
• 시간복잡도는 O(nlogn)이 된다.

결론

Merge Sort는 최악의 경우도 최선의 경우도 O(nlogn)의 시간 복잡도를 가진다. 최선의 경우 시간 복잡도가 O(n)인 Insertion Sort와 Shell Sort가 있지만 최악의 경우를 고려했을 때 Merge Sort가 좀 더 효율적이다. 다만 Bubble, Selection, Insertion Sort의 경우 추가적인 메모리 공간이 필요 없는 제자리 정렬이지만, Merge Sort는 임시로 데이터를 저장해야 하기 때문에 공간적 측면에서는 좋지 않다.

---

참고하면 좋은 사이트

[알고리즘] 합병 정렬(merge sort)이란 - Heee's Development Blog