[알고리즘] 병합 정렬(merge sort)

퀵소트를 만나기전까지 제일 이해가 안됐던 병합정렬을 기록한다.

 

병합정렬이란??

병합정렬은 분할정복(Divide & Conquer)정렬중 하나로, 특정 리스트를 분할하고, 정렬하여, 병합하는 일련의 과정을 거치며 정렬한다.

 

퀵 정렬은 피벗 값에 따라서 편향되게 분할할 가능성이 있다는 점에서 최악의 경우 O(N^2)의 시간 복잡도를 가지지만 병합 정렬은 정확히 반절씩 나눈다는 점에서 최악의 경우에도 O(N*logN)을 보장한다.

 

---

합병 정렬 또는 병합 정렬(merge sort)은 O(n log n) 비교 기반 정렬 알고리즘이다. 일반적인 방법으로 구현했을 때 이 정렬은 안정 정렬에 속하며, 분할 정복 알고리즘의 하나이다. 존 폰 노이만이 1945년에 개발했다. 하향식 합병 정렬에 대한 자세한 설명과 분석은 1948년 초 헤르만 골드스타인과 폰 노이만의 보고서에 등장하였다.
합병 정렬은 다음과 같이 작동한다.

1. 리스트의 길이가 1 이하이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는
2. 분할(divide) : 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
3. 정복(conquer) : 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
4. 결합(combine) : 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다. 이때 정렬 결과가 임시배열에 저장된다.
5. 복사(copy) : 임시 배열에 저장된 결과를 원래 배열에 복사한다.

출처 - 위키백과

---

 

병합정렬의 흐름

 

내 코드

import java.util.*;

public class Main {
    static int n;
    static int[] arr;
    static int index = 0;
    static int[] ret;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();

        arr = new int[n];
        for(int i = 0; i < n; i++){
            arr[i] = sc.nextInt();
        }

        ret = new int[n];
        //재귀의 첫 시작, 전체 범위를 지정한다.
        merge_sort(0, n-1);

        for(int number : ret){
            System.out.print(number + " ");
        }
    }

    static void merge_sort(int low, int high){
        //재귀함수의 종료지점, low와 high가 같아지면 break한다.
        if(low < high){
            int mid = (low + high) / 2;
            merge_sort(low, mid);
            merge_sort(mid+1, high);
            merge(low, mid, high);
        }
    }

    static void merge(int low, int mid, int high){
        int k = low;
        int i = low;
        int j = mid+1;

        //두 분할된 리스트를 작은값부터 채운다.
        while(i <= mid && j <= high){
            if(arr[j] < arr[i]){
                ret[k++] = arr[j++];
            }else{
                ret[k++] = arr[i++];
            }
        }

        //첫번째 리스트중 남은값을 채운다.(비교가 안됐으므로 그냥 넣어도 됨).
        while(i <= mid){
            ret[k++] = arr[i++];
        }

        //두번째 리스트중 남은값을 채운다.(비교가 안됐으므로 그냥 넣어도 됨).
        while(j <= high){
            ret[k++] = arr[j++];
        }
        
        //ret배열의 low부터 high까지의 결과를 원래 배열에 replace한다.
        for(int l = low; l <= high; l++){
            arr[l] = ret[l];
        }
    }
}