병합 정렬

삽입 정렬

병합 정렬은 더이상 쪼갤 수 없을 때까지 원소를 쪼개고 정렬하면서 합치는 방식입니다.

일단 원소들을 다 하나씩 되도록 쪼갭니다.

아래의 그림처럼 left와 right를 이용해서 mid를 기준으로 쪼개는 겁니다. mid는 left와 right의 중간 부분을 가리키고 있습니다.

이제 while문을 돕니다. while루프는 왼쪽 부분 리스트를 전부 다 돌았거나 오른쪽 부분 리스트를 전부 다 돌때까지 반복합니다. 그러니 L은 mid 이하까지 R은 right 이하까지 반복하는데 왼쪽 리스트, 오른쪽 리스트 하나라도 전부 반복이 되었다면 탈출합니다.

왼쪽 부분 리스트와 오른쪽 부분 리스트의 원소를 비교해서 더 작은 값이 합칠 리스트에 들어갑니다. 이 과정을 반복합니다.

4까지 넣고나면 한쪽 리스트가 모두 돌았으므로 while 문을 종료합니다.

이제 남은 반대쪽 리스트를 다 옮겨줍니다. 만약 L이 mid보다 크다면 왼쪽 부분 리스트가 tmp에 전부 넣어진 것이므로 오른쪽에 있는 부분 리스트의 값을 합쳐질 리스트에 집어넣습니다.

반대도 역시 똑같습니다. 오른쪽 부분 리스트가 전부 합쳐질 리스트에 넣어졌다면 R은 right보다 크게 될테니까 왼쪽 부분 리스트의 남은 값을 전부 합쳐질 리스트에 집어넣습니다.

이제 모든 비교와 교환은 끝났습니다. 오름차순으로 정렬이 된것을 볼 수 있습니다.

시간복잡도

리스트의 각 쪼개지는 단계별로 시간복잡도는 $2^i * n/2^i$ = $O(N)$
모든 단계의 수는 $log_2n$개 이므로 총 시간복잡도는 $O(NlogN)$

구현

import java.util.ArrayList;
import java.util.Collections;

public class MergeSort {
    public ArrayList<Integer> mergeFunc(ArrayList<Integer> leftList, ArrayList<Integer> rightList) {
        ArrayList<Integer> mergedList = new ArrayList<Integer>();
        Integer leftPoint = 0;
        Integer rightPoint = 0;

        // case1 - left/right 둘다 있을때
        while (leftList.size() > leftPoint && rightList.size() > rightPoint) {
            if (leftList.get(leftPoint) > rightList.get(rightPoint)) {
                mergedList.add(rightList.get(rightPoint));
                rightPoint += 1;
            } else {
                mergedList.add(leftList.get(leftPoint));
                leftPoint += 1;
            }
        }

        // case2 - right 데이터가 없을 때
        while (leftList.size() > leftPoint) {
            mergedList.add(leftList.get(leftPoint));
            leftPoint += 1;
        }

        // case3 - left 데이터가 없을 때
        while (rightList.size() > rightPoint) {
            mergedList.add(rightList.get(rightPoint));
            rightPoint += 1;
        }

        return mergedList;
    }

    public ArrayList<Integer> mergeSplitFunc(ArrayList<Integer> dataList) {
        if (dataList.size() <= 1) {
            return dataList;
        }
        int medium = dataList.size() / 2;

        ArrayList<Integer> leftArr = new ArrayList<Integer>();
        ArrayList<Integer> rightArr = new ArrayList<Integer>();

        leftArr = this.mergeSplitFunc(new ArrayList<Integer>(dataList.subList(0, medium)));
        rightArr = this.mergeSplitFunc(new ArrayList<Integer>(dataList.subList(medium, dataList.size())));

        return this.mergeFunc(leftArr, rightArr);
    }
}