Merge Sort (합병 정렬)

Merge Sort

• 분할 정복 알고리즘의 하나
• 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아 원래의 문제를 해결하는 전략
• 분할정복은 대개 재귀 호출을 이용하여 구현한다.
• 합병 정렬에서 실제로 정렬이 이루어지는 시점은 2개의 리스트를 합병(merge) 하는 단계이다.

 

Merge Sort는 크기 N인 배열을 입력으로 받아, 배열을 절반으로 두 개로 나눈 후,
각 작은 배열을 재귀적으로 정렬하고, 그 결과를 Merge한다.

 

 

과정

1. 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 본다.
2. 그렇지 않은 경우에는 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
3. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
4. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.

 

시간복잡도

• 자료의 개수 N을 2의 k제곱이라 가정했을 때, N = 8 = 2^3의 경우, 재귀 호출의 깊이가 3임을 알 수 있다.
• 이를 일반화하면 N = 2^k인 경우, k = log₂N으로 k번의 합병 단계를 거친다.
• 그리고 각각의 합병 단계에서는 최대 N번의 비교 연산을 수행한다.
• 따라서 N에 대한 병합 정렬의 시간복잡도는 O(NlogN)이다.

 

 

 

 

소스 코드

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
 
public class Main {
    public static List<Integer> numList = new ArrayList<>(Arrays.asList(100, 40, 60, 75, 77, 34, 51, 24, 24, 37, 88));
 
    public static void main(String[] args) {
        List<Integer> result = sort(numList);
        System.out.println(result);
    }
 
    static List<Integer> sort(List<Integer> numList) {
        if (numList.size() > 1) {
            return merge(sort(numList.subList(0, numList.size() / 2)),
                    sort(numList.subList(numList.size() / 2, numList.size())));
        } else {
            return numList;
        }
    }
 
    static List<Integer> merge(List<Integer> leftList, List<Integer> rightList) {
        List<Integer> mergeList = new ArrayList<>();
        int rightIndex = 0;
        for (int left : leftList) {
            while (rightList.size() > rightIndex && left > rightList.get(rightIndex)) {
                mergeList.add(rightList.get(rightIndex));
                rightIndex++;
            }
            mergeList.add(left);
        }
 
        for (int i = rightIndex; i < rightList.size(); i++) {
            mergeList.add(rightList.get(i));
        }
        return mergeList;
    }
}

 

 

[자료출처]

- https://velog.io/@widian/JAVA%EB%A1%9C-%EB%B3%91%ED%95%A9-%EC%A0%95%EB%A0%ACMerge-Sort%EA%B5%AC%ED%98%84%ED%95%98%EA%B8%B0.-21jtcjkoe2

- https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html