[Algorithm] Merge Sort (병합 정렬)

1. Merge Sort (병합 정렬)

 

병합 정렬은 divide and conquer를 기반으로 한 정렬 알고리즘이다. 정렬할 배열을 더이상 나누어지지 않을 때까지 반으로 나눈 뒤 다시 병합하면서 비교를 통해 정렬을 진행한다. 병합과정에서 비교하는 두 배열은 각각 이미 정렬되어 있는 배열들이다. 그렇기 때문에 각각 배열의 처음부터 더 작은 값을 선택하는 방식으로 병합하면서 정렬을 진행한다.

 

병합정렬의 진행 과정은 다음과 같다.

• divide: 정렬을 진행할 배열의 크기가 1이 될 때까지 대상이 되는 배열을 반으로 나누어 두 개의 부분 배열로 나눈다.
• conquer: 분할이 완료된 배열들을 재귀적으로 병합을 진행한다.
• combine: 병합시에 두개로 나누어진 부분 배열들의 값을 비교하여 하나의 정렬된 배열로 만든다.

 

2. Merge Sort 구현

 

divide and conquer 방식으로 진행하기 때문에 재귀함수를 통해서 배열을 나누고 병합하는 방식으로 구현한다. 이때 병합에서는 두 배열을 비교하여 하나의 임시 배열에 저장한 뒤 병합이 끝나면 기존의 배열의 위치에 정렬된 값을 다시 복사하도록 한다.

 

- Java를 이용한 Merge Sort 구현

import java.util.Arrays;

import Algorithm.Sorting.Sort;

public class MergeSort implements Sort {
    private int[] array;

    public MergeSort(int[] array) {
        this.array = Arrays.copyOf(array, array.length);
    }

    @Override
    public int[] sort() {
        divide(array, 0, array.length);
        return array;
    }

    private void divide(int[] arr, int l, int r) {
        if(r - l == 1) {
            return ;
        }

        //  배열을 2 부분으로 나눈다.
        divide(arr, l, (l + r) / 2);
        divide(arr, (l + r) / 2, r);

        // 두 부분 배열을 병합한다.
        merge(arr, l, (l + r) / 2, r);
    }

    private void merge(int[] arr, int l, int m, int r) {
        int N = r - l, left = l;
        int[] temp = new int[N];

        // 두 부분 배열을 병합한다.
        // 이때 정렬을 진행하여 임시 배열 temp에 저장한다.
        int index = 0;
        for(int i = m; i < r; i++) {
            if(l == m) {
                while(i < r) {
                    temp[index++] = arr[i++];
                }
                break;
            }

            while(l < m && arr[l] < arr[i]) {
                temp[index++] = arr[l++];
            }
            temp[index++] = arr[i];
        }

        while(l < m) {
            temp[index++] = arr[l++];
        }

        // 임시 배열 temp에 저장한 값을 원본 배열 arr로 복사한다.
        for(int i = 0; i < N; i++) {
            arr[left + i] = temp[i];
        }
    }
    
}

- src code: https://github.com/rmk1075/CS/tree/main/Algorithm/Sorting/MergeSort

 

3. Merge Sort 복잡도

- 시간 복잡도: O(N log N)

- 공간 복잡도: O(N)

 

 

[reference]

- https://www.geeksforgeeks.org/merge-sort/

Merge Sort - GeeksforGeeks