[알고리즘] 정렬 - 병합 정렬

1. 개념

하나의 배열을 크기가 같은 2개의 배열로 분할한다. 분할은 분할 대상의 배열 길이가 2이상이면 계속 반복하다 분할 대상 배열 길이가 1이하가 되면 반복을 멈춘다.

분할된 배열을 병합하는데, 정렬을 하면서 병합을 진행한다. 병합을 진행할 때는 병합 대상이 되는 2개의 배열 각각에 포인터를 두고, 포인터가 가리키는 원소 중 더 작은 것을 병합 결과 배열에 놓고, 병합 결과 배열에 놓인 원소의 포인터는 증가시킨다. 

 

2. 특징

• 분할 정복 방법이 적용된다. 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다. 각각을 해결할 때는 재귀적으로 함수 호출을 진행하여 해결한다.
• 만약 배열로 데이터를 다루면 제자리 정렬이 아니다. 병합된 내용을 담을 추가 메모리가 필요하다.
• 만약 연결리스트로 데이터를 다루면 제자리 정렬이 가능하다. 링크 연결만 바꿔주면 되기 때문이다.
• 입력 데이터의 분포에 크게 영향을 받지 않고 시간복잡도가 O(nlogn)이다.
• 안정 정렬이다.

 

3. 시간복잡도

1) 분할할 때

그냥 자르기만 하면 되기 때문에 비교와 이동이 일어나지 않는다

2) 병합할 때

ⓛ 비교 횟수

원소 개수가 8개라고 하자.

• 길이가 1인 배열 2개를 길이가 2인 배열로 병합할 때 각 배열에 있는 포인터가 가리키는 원소끼리 비교해서 작은 걸 구하고, 그 다음에 또 포인터가 가리키는 원소를 살펴서 작은 걸 구한다. 포인터가 밖으로 나가있는지는 알 수가 없으니 비교는 2회 일어난다. 
  • 한 단계에서 위와 같은 병합이 총 4번 진행되니 총 비교 횟수는 8회이다.
• 길이가 2인 배열 2개를 길이가 4인 배열로 병합할 때 위와 같은 원리로 비교는 4회 일어난다.
  • 한 단계에서 위와 같은 병합이 총 2번 진행되니 총 비교 횟수는 8회이다.
• 이를 쭉 진행해 나가면 결국 비교 횟수는 원소개수*병합횟수가 된다.

병합 횟수는 길이가 1인 배열을 길이가 2인 배열로 병합하는 1번, 길이가 2인 배열을 길이가 4인 배열로 병합하는 2번, 길이가 4인 배열을 길이가 8인 배열로 병합하는 3번 이루어져서 총 3번이다. 이를 일반화하면 log2n 번 일어난다고 할 수 있다. 여기서 2는 작은 2를 의미한다.

따라서 총 비교 횟수는 nlogn이다.

 

② 이동 횟수

모든 원소를 임시 배열에 이동하는 횟수 n번, 임시 배열에 있는 것을 원래 배열로 다시 가져오는 횟수 n번으로 한 번의 병합이 이루어질 때 총 2n번의 이동이 이루어진다. 병합 횟수는 위에서 구한 것과 같이 log2n번이다.

따라서 총 이동 횟수는 2nlogn이다.

 

이를 고려했을 때 병합정렬의 시간복잡도는 O(nlogn)이라고 할 수 있다.

 

4. 코드

import java.io.*;
// top-down 방식
// 전체 배열을 절반씩 쪼개나간다

public class Main {
    private static int[] sorted = new int[5];

    public static void main(String[] args) throws IOException{
        int[] nums = {5, 1, 2, 6, 9};
        mergeSort(nums, 0, nums.length-1);

        for(int num : nums){
            System.out.println(num);
        }

    }


    private static void mergeSort(int[] nums, int left, int right){
        if(left == right) return;

        int mid = (left + right) / 2;

        mergeSort(nums, left, mid);
        mergeSort(nums, mid+1, right);

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

    private static void merge(int[] nums, int left, int mid, int right){
        int l = left;
        int r = mid+1;
        int idx = left;

        while(l <= mid && r <= right){
            if(nums[l] <= nums[r]){
                sorted[idx] = nums[l];
                idx++;
                l++;
            }else{
                sorted[idx] = nums[r];
                idx++;
                r++;
            }

        }
        if(l > mid){
            while(r <= right){
                sorted[idx] = nums[r];
                idx++;
                r++;
            }
        }else{
            while(l <= mid){
                sorted[idx] = nums[l];
                idx++;
                l++;
            }
        }
        for(int i = left; i<= right; i++){
            nums[i] = sorted[i];
        }
    }

}

import java.io.*;
// bottom-up 방식
// 원소 1개인 것부터 진행
// 재귀 피할 수 있는 방법

public class Main {
    private static int[] sorted = new int[5];

    public static void main(String[] args) throws IOException{
        int[] nums = {5, 1, 2, 6, 9};
        mergeSort(nums, 0, nums.length-1);

        for(int num : nums){
            System.out.println(num);
        }

    }


    private static void mergeSort(int[] nums, int left, int right){
        for(int size = 1; size <= right; size += size){
            for(int l = 0; l<=right-size; l+= (2 * size)){
                int low = l;
                int mid = l+size-1;
                int high = Math.min(l+(2*size) - 1, right);
                merge(nums, low, mid, high);
            }
        }
    }

    private static void merge(int[] nums, int left, int mid, int right){
        int l = left;
        int r = mid+1;
        int idx = left;

        while(l <= mid && r <= right){
            if(nums[l] <= nums[r]){
                sorted[idx] = nums[l];
                idx++;
                l++;
            }else{
                sorted[idx] = nums[r];
                idx++;
                r++;
            }

        }
        if(l > mid){
            while(r <= right){
                sorted[idx] = nums[r];
                idx++;
                r++;
            }
        }else{
            while(l <= mid){
                sorted[idx] = nums[l];
                idx++;
                l++;
            }
        }
        for(int i = left; i<= right; i++){
            nums[i] = sorted[i];
        }
    }

}

5. 관련 문제

백준 2751

GitHub - Lee-Min-Jung/coding_test_practice

백준 1751

GitHub - Lee-Min-Jung/coding_test_practice