[정렬 알고리즘]Merge Sort

합병 정렬 알고리즘 - Merge Sort

이 알고리즘을 뒷받침하는 개념은 실제로 합병과 정렬, 분할 이 세 가지 조합으로 이루어져 있다. 

배열을 0 또는 1개의 요소로 구성된 더 작은 배열로 분해한 다음 새로운 정렬 배열을 작성한다.

시각적으로 살펴보자.

배열을 1,2,3 단계를 걸쳐서 0 또는 1개의 요소로 구성된 작은 배열로 만들어 주었다. 4단계에서 정렬되면서 합쳐진다. 5단계에서도 마찬가지. 분해한 것들을 모두 합침으로써 정렬된 배열이 나온다. 

개별적인 배열이라는 것을 각각의 색상으로 표현되었다. 

최종적으로 합병 정렬은 배열이 정렬되어 있다고 가정하고 정렬된 두 개의 조합을 반환하면 된다. 직접 구현해보자.

기능을 구현하기 위해

정렬된 두 배열 합병을 담당할 기능 즉, 함수를 구현하는 것이 유용하다.

정렬된 두 배열이 주어지면, 이 헬퍼 함수는 정렬된 새 배열을 생성해야하며, 입력으로 들어온 두 배열의 모든 요소로 구성돼야 한다.

이 함수는 O(n+m) 시간 및 O(n+m) 공간에서 실행되어야 하며 전달된 parameter를 수정해서는 안된다.

n은 첫 번째 배열, m은 두 번째 배열

의사코드

• 빈 배열을 만들고, 각 배열에서 가장 작은 값을 확인한다.
• 첫 번째 배열의 값이 두 번째 배열 값보다 작으면 첫 번째 배열의 값을 결과에 밀어 넣고 다음 값으로 이동
• 두 번째 배열의 값이 더 작은 경우 두 번째 배열의 값을 결과로 밀어 넣고 다음 값으로 이동
• 배열 하나를 완료한 다음에는 다른 배열의 남은 값을 모두 넣는다.

function merge(arr1, arr2) {
    let results = [];
    let i = 0;
    let j = 0;
    // 둘 모두를 반복할 때만 적용됨.
    while ( i < arr1.length && j < arr2.length) {
        if(arr2[j] > arr1[i]) {
            results.push(arr1[i]);
            i++;
        } else {
            results.push(arr2[j]);
            j++;
        }
    }
    return results;
}

merge([1,10,50], [2,14,99,100])
// results: [1, 2, 10, 14, 50]

배열의 마지막에 도달하였기에 루프가 종료된다. 배열 하나를 끝낸 다음 j에 남은 모든 값을 추가해야 한다.

반대의 경우가 될 수도 있다. while 루프를 추가하여 남은 배열을 push 해준다.

function merge(arr1, arr2) {
    let results = [];
    let i = 0;
    let j = 0;
    // 둘 모두를 반복할 때만 적용됨.
    while (i< arr1.length && j < arr2.length) {
        if(arr2[j] > arr1[i]) {
            results.push(arr1[i]);
            i++;
        } else {
            results.push(arr2[j]);
            j++;
        }
    }
    while (i < arr1.length) {
        results.push(arr1[i]);
        i++;
    }
    while (j < arr2.length) {
        results.push(arr2[j]);
        j++;
    }
    return results;
}

merge([1,10,50], [2,14,99,100])
// results: [1, 2, 10, 14, 50, 99, 100]

정렬된 두 배열을 이용한 간단한 합병 정렬이 구현되었다. 이제는 분할부터 하여 합병까지 제대로 된 합병 정렬을 구현해보자.

1. 배열이 비어 있거나 하나의 요소를 가질 때까지 배열을 반으로 나눈다.
2. 작은 배열이 준비되면 작성해 놓았던 합병 함수를 사용해 전체 배열 길이가 될 때까지 합쳐나간다.
3. 가장 마지막에 합병된 배열을 반환한다. 

function mergeSort(arr) {
    if(arr.length <= 1) return arr;
    let mid = Math.floor(arr.length/2);
    let left = mergeSort(arr.slice(0, mid));
    let right = mergeSort(arr.slice(mid));

    return merge(left,right);
}

mergeSort([10,24,16,39])

해당 배열 [10, 24, 39, 16] 4개의 요소를 가지를 배열을 가지고 설명해보겠습니다.

재귀 함수를 사용하였음으로 색상을 달리하여 함수를 구분하였습니다.

 

1. mergeSort가 실행되고 매개변수인 arr에 [10, 24, 39, 16]이 들어오게 됩니다.

2. 배열의 길이가 1보다 작거나 같으면 arr를 그대로 반환한다. 조건에 부합하지 않기에 다음 줄을 실행한다.

3. 배열의 길이가 4이기에 절반인 2가 mid값으로 들어간다. mid = 2;

4. let left = mergeSort(arr.slice(0,2)); 이 말은 잘라낸 배열을 재귀 함수의 인자로 집어넣는 것이다. 그렇다면 호출 스택에 

mergeSort가 쌓이면서 인자 값으로 [10,24]가 들어온다.

5. 똑같이 조건문이 실행될 것이며 조건에 부합하지 않기에 [10,24] 길이의 절반인 mid 값 1을 가진다.

6. mergeSort가 또 한 번 실행되며 이번엔 [10]이 인자로 들어가며 조건문에 부합하게 된다. 그렇다면 return [10]을 하며 해당 mergeSort가 종료되며 mergeSort의 left 값에 배열 [10]이 들어가게 된다. 그런 다음에 right 값을 찾는다.

7. ritght에서 mergeSort가 실행되며 인자로 [24]가 들어간다. 조건문에 부합하며 해당 arr를 리턴하며 right에 [24]가 들어간다. 

8. left와 right 값을 가지고 있으니 merge(left, right)가 실행된다. left엔 [10], right엔 [24]. merge 함수는 [10,24]를 리턴하며,

mergeSort의 left값에 [10, 24]가 들어온다. 해당 mergeSort는 right 줄에 [39, 16]을 인자로 mergeSort를 호출한다.

9. 이 또한 조건에 부합하지 않기에 위와 같은 작업을 동일하게 하면서 left는 [39], right는 [16]을 가지며 merge([39],[16])을 실행하게 된다. 해당 merge는 [16,39]를 리턴하며 mergeSort는 left [10, 24], right [16,39]를 가지며 merge를 실행한다.

10. 최종적으로 [10, 16, 24, 39] 정렬된 배열을 리턴한다.

 

Merge Sort의 Big O

Time Complexity(Best)	Time Complexity(Average)	Time Complexity(Worst)	Space complexity
O(n log n)	O(n log n)	O(n log n)	O(n)

 

n log n인 이유가 무엇일까?

만약 32개의 항목을 1 또는 0 요소가 될 때까지 나눈다면 

16 16 => 8 8 8 8 => 4 4 4 4 4 4 4 4 => 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 => 1 1 1...

n이 32로 늘어나면 5번 분할한다. 8일 때는 3번 분할한다. 이것이 밑이 2인 log n이다. 

배열에서 n 길이가 늘어나면 log n의 비율로 분할 횟수가 늘어난다. 그러면 n log n은 무엇일까?

매번 분할할 때마다 합병을 실제로 수행하려면 O(n)의 비교가 필요하다. n이 8개라면 8번의 비교가 필요한 것이다.

 

데이터에 구애받지 않는 정렬 알고리즘을 원한다면, 최선은 O(n log n)이다. 그러니 합병 정렬은 좋다.

합병 정렬은 배열이 클수록 메모리에 더 많은 배열을 저장해야 한다. 버블 정렬보다 많은 공간을 차지한다.