MergeSort(합병정렬)

MergeSort란?

합병정렬은 분할과 정복으로 정렬하는 방법으로서, O(nlogn)로 정렬 속도가 빠르다.

입력이 2개의 부분문제로 분할되고, 부분문제의 크기가 1/2로 감소한다.

분할하는 부분은 중간 인덱스 계산과 2회의 순환 호출이므로 O(1) 시간이 소요된다.

합병 수행시간은 입력의 크기에 비례한다. 

2개의 정렬된 배열 A와 B의 크기가 각각 m과 n이라면, 최대비교횟수 = (m+n-1)으로, 시간복잡도는 O(m+n) => O(n)

층수는 k번 1/2로 분할했으면 k개의 층이 생기는 것이고, 입력의 크기가 n일 때 2^k = n으로부터 k는 logn임을 알 수 있다.

따라서 합병정렬의 시간복잡도는 O(nlogn)이다.

 

단점! 공간복잡도가 O(n)이다. 2개의 정렬된 부분을 하나로 합병하기 위해, 합병된 결과를 저장할 곳이 필요하기 때문이다.

 

 

data가 [5, 10, 66, 77, 54, 32, 11, 15]라고 가정한다.

분할

[5, 10, 66, 77, 54, 32, 11, 15]

 

[5, 10, 66, 77], [54, 32, 11, 15]

[5, 10], [66, 77], [54, 32], [11, 15]

[5], [10], [66], [77], [54], [32], [11], [15]

 

정복

[5, 10], [66, 77], [32, 54], [11, 15]

정렬되어 있는 상태이기 때문에 첫번째 그룹과 두번째 그룹의 0번째 항을 비교한다.

1회차 [10], [66, 77], [32, 54], [15]

[5], [11]

 

2회차 [], [66, 77], [32, 54], []

[5, 10], [11, 15]

 

3회차 [], [], [], [] 이미 정렬된 상태이므로 그대로 가져온다.

[5, 10, 66, 77], [11, 15, 32, 54]

 

4회차 [5, 10, 66, 77], [11, 15, 32, 54]

[5]

 

5회차 [10, 66, 77], [11, 15, 32, 54]

[5, 10]

 

6회차 [66, 77], [15, 32, 54]

[5, 10, 11]

 

7회차 [66, 77], [32, 54]

[5, 10, 11, 15]

 

8회차 [66, 77], [54]

[5, 10, 11, 15, 32]

 

9회차 [66, 77], []

[5, 10, 11, 15, 32, 54]

 

10회차 [], [] 이미 정렬된 상태이므로 그대로 가져온다.

[5, 10, 11, 15, 32, 54, 66, 77]

 

코드

let data = [5, 10, 66, 77, 54, 32, 11, 15];

function mergeSort(arr) {
    let arrLen = arr.length;
    let result = [];
    if (arrLen <= 1) {
        return arr;
    }
    let middle = parseInt(arrLen / 2)
    let group1 = mergeSort(arr.slice(0, middle));
    let group2 = mergeSort(arr.slice(middle));

    while (group1.length != 0 && group2.length != 0) {
        // 원소 값이 0이면 그냥 바로 뒤에 붙여주면 되기 때문이다.
        if (group1[0] < group2[0]) {
            result.push(group1.shift());
        } else {
            result.push(group2.shift());
        }
    }

    while (group1.length != 0) {
        result.push(group1.shift());
    }

    while (group2.length != 0) {
        result.push(group2.shift());
    }
    return result;
}

console.log(mergeSort(data));

 

 

pop() 메서드는 배열에서 마지막 요소를 제거하고 그 요소를 반환한다. 

shift() 메서드는 배열에서 첫 번째 요소를 제거하고, 제거된 요소를 반환한다. 이 메서드는 배열의 길이를 변하게 한다.

가장 작은 것을 가져와야하기 때문에, 첫번째 요소에 접근해야 하고, shift()를 사용한다.