[알고리즘] 병합 정렬(Merge sort) 알아보기

안녕하세요😎 백엔드 개발자 제임스입니다 :)
오늘 포스팅 내용은 병합 정렬(Merge sort)입니다. 저번 시간엔 분할 정복 알고리즘에 대해서 정리를 했는데요. 분할 정복 알고리즘의 대표적인 예가 병합 정렬이라고 할 수 있습니다. 또한 분할 정복 알고리즘을 설명했을 때 사용된 그림 예시 또한 병합 정렬과 동일합니다.

---

분할 정복 알고리즘에서 사용된 그림 예시

분할 정복 알고리즘 다시 알아보기 (아래 링크 클릭)

https://kang-james.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B6%84%ED%95%A0-%EC%A0%95%EB%B3%B5Divide-and-Conquer-%EC%95%8C%EC%95%84%EB%B3%B4%EA%B8%B0

[알고리즘] 분할 정복(Divide and Conquer) 알아보기

---

---

병합 정렬(Merge sort)

---

병합 정렬은 정렬되지 않은 배열이 있을 때, 나눌 수 없을 때까지 나눈 뒤 어떠한 종료 조건에서 값을 반환하고 나누어진 배열들을 다시 결합하며 정렬을 하는 방식입니다. 위에 분할 정복 알고리즘에서 사용된 그림 예시를 참고하면 좋겠습니다.

* 병합 정렬은 합병 정렬, Merge sort라고도 불립니다.

위에 게시된 그림을 보았을텐데요. 여기서 중요한 것은 결합을 진행하면서 각각 부분 배열(리스트)들은 '정렬된 상태'가 된다는 것입니다.
그렇다면 어떻게 정렬이 되는 것일까요? 이때 우리가 이미 알고있던 버블 정렬, 삽입 정렬 등이 사용되지 않습니다. 아래에서 자세하게 알아보도록 하겠습니다.

1. 병합 정렬 과정

• Split 단계
• Merge 단계 (Left Array, Right Array)

 

2. 정렬되는 과정 자세하게 보기

기존에 정렬되지 않은 [4, 6, 3, 5, 2, 1] 배열을 위 그림에서처럼 모두 나누었다고 가정해보겠습니다. 이제 결합을 진행할 것인데요. 저희는 결합하며, 정렬되는 과정을 알아볼 예정입니다.

원리

결합되는 원리는 이렇습니다. 나누어진 배열들을 왼쪽 배열과 오른쪽 배열로 나누어서 두개를 비교하는데요. 이때 0번 인덱스를 시작으로 비교합니다.

1) 부분적으로 정렬된 배열이 두개 있습니다. 이제 각 배열의 인덱스 0번 데이터를 비교합니다.

• 왼쪽 배열 0번 인덱스와 오른쪽 배열 0번 인덱스 중에 작은 값을 새로운 배열에 추가합니다.

 

2) 오른쪽 배열의 값을 넣었으므로, 다음은 오른쪽 배열의 인덱스를 1증가 시키킨 뒤 다시 비교합니다.

 

• 왼쪽 배열 0번 인덱스와 오른쪽의 다음 인덱스 1번과 비교했을 때 동일하게 작은 값을 새로운 배열에 추가합니다.
• 이번에도 오른쪽 배열의 값으로 추가되었습니다.

 

3) 이번에는 왼쪽 배열 인덱스 0번과 오른쪽 배열 인덱스 2번과 비교합니다.

• 이번에는 왼쪽 배열 0번 인덱스의 값이 더 작으므로, 왼쪽의 값을 새로운 배열에 추가합니다.

 

4) 동일하게 왼쪽 배열과 오른쪽 배열을 인덱스 순차별로 비교하고, 작은 값을 새로운 배열에 추가합니다.

• 이렇게 비교를 모두 마치면, 최종적으로 정렬된 배열이 나오게 됩니다.

 

---

병합 정렬은 분리가 모두 완료된 순간부터 위와 같이 정렬과 결합을 진행하며, 최종적인 모습을 만들어 냅니다. 그리고 이 모든 과정을 재귀 함수로 구현됩니다.

3. 코드로 보는 병합 정렬

병합 정렬은 재귀 함수로 구현되며, 두 가지 기능으로 구현됩니다.
1) Split
2) Merge

참고 메서드 : ArrayList<> subList(int index, int index2)
-> List를 자르는 메서드
-> 원본 리스트의 index 부터 index2 한칸 앞 부분까지 잘라서 반환
-> {1, 2, 3, 4, 5} 의 리스트에서 subList(0, 3) 을 진행하면, { 1, 2, 3 } 을 반환

---

#1 split Function

/**
 * split & merge function
 * @return 모두 분리된 배열을 merge
 */
public ArrayList<Integer> splitFunc(ArrayList<Integer> array) {

    if(array.size() <= 1) { // 재귀 함수의 종료 조건( 크기가 1 이하 일 때 array 반환)
        return array;
    }

    int medium = array.size() / 2;

    ArrayList<Integer> leftArr;
    ArrayList<Integer> rightArr;

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

    return mergeFunc(leftArr, rightArr); // mergeFunc 반환
}

 

#2 merge Function

/**
 * merge function
 * @return 결합하며 정렬된 배열 반환
 */
public ArrayList<Integer> mergeFunc(ArrayList<Integer> leftArr , ArrayList<Integer> rightArr) {

    ArrayList<Integer> mergedList = new ArrayList<>(); // 결합 시에 저장될 배열

    int leftPoint = 0;
    int rightPoint = 0;

    // CASE 1 : left 와 right 둘다 있을 때
    while (leftArr.size() > leftPoint && rightArr.size() > rightPoint) {

        if(leftArr.get(leftPoint) > rightArr.get(rightPoint)) {
        
            mergedList.add(rightArr.get(rightPoint));
            rightPoint++;
            
        } else {
            mergedList.add(leftArr.get(leftPoint));
            leftPoint++;
        }
    }

    // CASE 2 : left 만 있을 때
    while (leftArr.size() > leftPoint) {

        mergedList.add(leftArr.get(leftPoint));
        leftPoint++;
    }

    // CASE 3 : right 만 있을 때
    while (rightArr.size() > rightPoint) {

        mergedList.add(rightArr.get(rightPoint));
        rightPoint++;
    }

    return mergedList;
}

 

#3 실행

public static void main(String[] args) {

    MergeSort2 test = new MergeSort2();

    ArrayList<Integer> array = new ArrayList<Integer>(Arrays.asList(3,5,6,7,2,1)); 
    
    // array = [3,5,6,7,2,1]

    System.out.println(test.splitFunc(array)); // 1, 2, 3, 5, 6, 7

}

 

4. 시간 복잡도

* 요약
1) 병합 정렬의 시간 복잡도는 O(N * logN)
2) 최악의 경우여도 시간 복잡도는 O(NlogN) 동일
3) 기존의 데이터를 담을 추가적인 배열 공간이 필요하기 때문에 다소 비효율적인 공간 복잡도

마지막으로 시간 복잡도를 정리하기 전에 병합 정렬의 과정을 다시 알아보겠습니다.

1) [분할] 리스트의 길이가 1이 될 때까지 반복적으로 반으로 나눕니다.
2) [병합] 모두 나누어지면, 분할된 리스트들을 다시 합칩니다. 이때 정렬도 동시에 진행됩니다.

아래부터는 우리가 병합 정렬을 이해하기 위해 구현했던 그림 예시를 통해서 시간복잡도를 구해보도록 하겠습니다.

---

#1 분할 과정 시간 복잡도

• 가장 위 정렬이 되지 않은 리스트에 N개 데이터가 들어있습니다.
• 좌측에 보이는 숫자는 분할과 병합을 각각 진행한 뒤에 나온 리스트의 개수입니다.

병합 정렬에서 분할은 항상 리스트의 중앙을 기점으로 1/2 씩 나뉘는 것입니다. 그렇게 리스트의 크기가 1이 될 때까지 분해를 하는 것인데요. 따라서 N개 데이터를 모두 분해하기 위해서는 2ⁿ 에서 지수 n 번 나누어야 합니다. 위 그림에서는 N이 6인 리스트를 모두 분해하기 위해서 3번 나눈 것을 알 수 있습니다.

이를 일반화한다면, n = log₂N 이 됩니다. 따라서 분해 과정에서 발생하는 시간 복잡는 O(logN)이 됩니다.

 

#2 병합 과정 시간 복잡도

병합 과정은 두 가지를 고려해야 합니다. 첫 번째는 분해된 리스트가 결합하는 과정입니다. 그리고 두번째는 결합할 때  동시에 진행되는 정렬 과정입니다.

#2-1 결합

결합 과정은 위에서 알아본 분해 과정을 다시 반대로 하는 것이기에 시간 복잡도는 O(logN)으로 동일합니다.

#2-2 정렬

정렬 과정은 분해된 두 리스트를 0번 인덱스부터 시작하여 한 개씩 비교하며 정렬하는 방식인데요. 아래 예시로 보았을 때 N개 데이터를 정렬하기 위해서 N번 비교를 진행한다는 것을 알 수 있습니다. 따라서 이 때 발생하는 시간 복잡도는 O(N)이 됩니다.

 

 

#3 최종 시간 복잡도

최종적으로 병합 정렬의 시간 복잡도를 구해보겠습니다.

단계별로 구한 시간 복잡도는 각각 O(logN) , O(logN), O(N) 입니다. 이어서 케이스들을 모두 합치면, logN * logN * N 으로 최종 시간 복잡도는 O(NlogN) 입니다.

병합 정렬(Merge sort)의 시간 복잡도 O(NlogN)