Merge Sort(병합 정렬)

Merge Sort(병합 정렬)

정의

여러 개의 정렬된 자료의 집합을 결합하여 한 개의 정렬된 집합으로 만드는 방법

1단계

|60, 10, 30, 2, 16, 8, 31, 22|

8개의 데이터가 처음에는 하나의 집합으로 존재한다.

|60, 10, 30, 2|, |16, 8, 31, 22|

2등분으로 분리

|60, 10|, |30, 2|, |16, 8|, |31, 22|

그리고 또 분리

|60|, |10|, |30|, |2|, |16|, | 8|, |31|, |22|

더 이상 쪼갤 수 없을 때 까지 각각 1개의 원소로 분리된다.

2단계 : 합치면서 정렬하기 !!

|10, 60|, |2, 30|, |8, 16|, |22, 31|

다시 4개의 부분 집합으로 합쳐졌는데 아까와는 달리 각 부분집합들이 정렬된 상태로 합쳐진다.

(작은 숫자가 앞에 큰 숫자를 뒤에)

|2, 10, 30, 60|, |8, 16, 22, 31|

각 배열 내에서 가장 작은 값 2개를 비교, 다시 크기 순으로 정렬되면서 병합

|2, 8, 10, 16, 22, 30, 31, 60|

정렬 완성 !!

시간 복잡도

• 알고리즘은 큰 그림에서 보면 분할 단계와 병합 단계로 나눌 수 있으며, 단순히 중간 인덱스를 찾아야 하는 분할 비용 보다 모든 값들을 비교하는 병합 비용이 크다.

• 전반적인 반복의 수는 절반으로 줄어들기 때문에 O(logN) 시간이 필요하고, 각 패스에서 병합할 때 모든 값을 비교하므로 O(N) 시간이 소모된다.

• 따라서 Merge Sort는 모든 케이스에 대해 O(NlogN)을 갖는다.

소스코드

먼저 배열을 나눌 수 없을 때 까지 분할한 후에, 다시 병합하면서 점점 큰 배열을 만들어 나간다.

입력 배열의 크기가 2보다 작으면 그대로 반환(값을 비교할 필요가 없기 때문에)        

import java.util.Arrays;

public class _2751 {
	static int[] tmp;
    public static void main(String[] args) {
        _2751 main = new _2751();
        main.go();
    }

    private void go() {
        int[] array = {60, 10, 30, 2, 16, 8, 31, 22};
        tmp = new int[array.length];
        int len = array.length;
        mergeSort(array, 0, len - 1);
    }

    private void mergeSort(int[] arr, int low, int high) {
        int mid;
        if (low < high) {
            mid = (low + high) / 2;
            mergeSort(arr, low, mid); // 배열을 쪼개는 재귀함수
            mergeSort(arr, mid + 1, high); // 배열을 쪼개는 재귀함수
            merge(arr, low, mid, high);
        }
    }

    private void merge(int[] arr, int low, int mid, int high) {
        int index = low, p1 = low, p2 = mid + 1;
        while (p1 <= mid && p2 <= high) {
            if (arr[p1] < arr[p2]) {
                tmp[index++] = arr[p1];
                p1++;
            } else {
                tmp[index++] = arr[p2];
                p2++;
            }
        }

        if (p1 > mid) { // p1 포인터가 배열을 먼저 채운 경우
            for (int i = p2; i <= high; i++) // 남은 p2 포인터 모두 사용
                tmp[index++] = arr[i]; 
        } else { // p2 포인터가 배열을 먼저 채운 경우
            for (int i = p1; i <= mid; i++) // 남은 p1 포인터 모두 사용
                tmp[index] = arr[i];
        }

        for (int i = low; i <= high; i++) {
            arr[i] = tmp[i];
        }
        System.out.println(Arrays.toString(arr));
    }
}