merge sort

merge sort

---

• merge sort(병합정렬)는 분할 정복(Devide and Conquer)알고리즘의 하나이다.
• 분할과 병합의 두 단계로 나눌 수 있다.
  • 분할 : 분할되지 않은 크기까지 분할하기. (리스트의 크기가 1이 될 때까지)
  • 병합 : 분할된 데이터를 단계별로 합치기. 합치는 과정은 이하와 같이 2개의 리스트의 값들을 처음부터 하나씩 비교하여 두 개의 리스트의 값 중에서 더 작은 값을 새로운 리스트로 옮기는 처리를 반복하여 진행된다. 

 

알고리즘 이해하기

---

[3, 4, 9, 2]라는 데이터를 가진 배열이 병합정렬되는 과정은 이하와 같다.

1. [3, 4, 9, 2] → [3, 4]와 [9, 2]로 분할

2. [3, 4] → [3]과 [4]로 분할

3. [3]과 [4] → [3, 4]로 병합 

4. [9, 2] → [9]와 [2]로 분할

5. [9]와 [2] → [2, 9]로 병합

6. [3, 4]와 [2, 9] → [2, 3, 4, 9]로 병합

 

merge sort 구현해 보기

---

import java.util.ArrayList;

public class MergeSort {

    public ArrayList<Integer> mergeSort(ArrayList<Integer> mergeArr) {
        if (mergeArr.size() <= 1) {
            return mergeArr;
        }

        //재귀함수를 사용하여 list의 size가 1이 될때까지 분할을 진행
        int medium = mergeArr.size() / 2;
        ArrayList<Integer> leftArr = this.mergeSort(new ArrayList<>(mergeArr.subList(0, medium)));
        ArrayList<Integer> rightArr = this.mergeSort(new ArrayList<>(mergeArr.subList(medium, mergeArr.size())));

        //list의 size가 1이 된것들부터 병합을 진행
        return this.mergeList(leftArr, rightArr);
    }

    public ArrayList<Integer> mergeList(ArrayList<Integer> leftArr, ArrayList<Integer> rightArr) {
        ArrayList<Integer> mergedList = new ArrayList<>();
        int leftIndex = 0;
        int rightIndex = 0;

        //왼쪽 list와 오른쪽 list가 모두 남아있을 때
        while (leftArr.size() > leftIndex && rightArr.size() > rightIndex) {
            if (leftArr.get(leftIndex) < rightArr.get(rightIndex)) {
                mergedList.add(leftArr.get(leftIndex));
                leftIndex++;
            } else {
                mergedList.add(rightArr.get(rightIndex));
                rightIndex++;
            }
        }

        //왼쪽 list만 남아있을 때
        if (leftArr.size() > leftIndex) {
            mergedList.addAll(new ArrayList<>(leftArr.subList(leftIndex, leftArr.size())));
        }

        //오른쪽 list만 남아있을 때
        if (rightArr.size() > rightIndex) {
            mergedList.addAll(new ArrayList<>(rightArr.subList(rightIndex, rightArr.size())));
        }

        return mergedList;
    }

}