Merge Sort (합병정렬)

합병 정렬은 빠르지만 조금 더 어렵다. 아주 유명한 방식이다.

1948년 폰 노이만이 최초의 합병 정렬 프로그램을 작성했다.

합병정렬은 두 가지 조합으로 되어 있다.

1. 합병
2. 정렬

0개나 1개의 요소로 된 배열은 이미 정렬되어 있다는 점을 이용한다.

배열을 더 작은 하위 배열로 나눈다.

만약 8개의 요소가 있는 배열이라면 8개의 단일 요소 배열로 분할한 다음 다시 병합시킨다.

정렬된 두 배열을 합병하는 방법

정렬된 두 배열을(둘다 같은 방식으로 정렬되어야 한다. 하나는 오름차순, 하나는 내림차순이면 안된다)

합병하는 방식은 O(n+m) 시간, O(n+m) 공간이 필요하다.

n은 첫번째 배열의 크기, m은 두번째 배열의 크기이다.

1. 빈 배열을 만들고 각 배열에서 가장 작은 요소부터 시작한다.
2. 카운터는 2개를 쓴다. i, j. 각각 하나의 배열을 맡는다. while 루프를 쓰기를 권장.
3. 첫번째 배열의 첫번째 항목을 두번째 배열의 첫번째 항목 값과 비교
4. 첫번째 항목이 더 작다면 결과 배열에 집어넣고 다음 항목으로 넘어간다.
5. 첫번째 항목이 더 크다면 두번째 배열의 값을 취하여 결과 배열에 넣고 두번째 배열의 다음 값으로 넘어간다.
6. 배열 하나를 완료하면 그 다음 남은 배열의 값을 모두 넣는다.

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) {  // 첫 while루프에서 끝가지 갔다면 실행되지 않음.
        results.push(arr2[j])
        j++;
    }
    return results;
}
merge([100,200], [1,2,3,5,6])

합병정렬 구현

개념적으로 이해하기 조금 어렵다.

대부분의 합병 정렬 구현 시 재귀를 사용하기 때문.

• 목표는 배열을 계속 반으로 나누는 것.
• 0 또는 1개의 요소만 가진 배열이 될때까지. arr.slice를 쓴다.
• 다 나눠지면 앞에서 작성한 합병 함수를 사용해 다시 합친다.
• 이것들을 재귀적으로 구현한다.

function mergeSort(arr){
    if(arr.length <= 1) return arr;        // 재귀함수를 쓸때 중단점. 길이가 1보다 작거나 같으면
    let mid = Math.floor(arr.length/2);  // 가운데 지점을 만들고.
    let left = mergeSort(arr.slice(0,mid));    // 왼쪽은 0부터 중간점까지를 재귀함수
    let right = mergeSort(arr.slice(mid));      // 오른쪽도 마찬가지.
    return merge(left, right);  // 앞에서 만든 merge 함수.
}

mergeSort([10,24,76,73])

도표로 그려본다면 이렇게 된다.

합병정렬의 Big-O

최악의 경우 → O(n log n)

평균의 경우 → O(n log n)

최선의 경우 → O(n log n)

공간복잡도 → O(n)

합병 정렬은 대상이 무엇이든 차이가 없다. 예외 케이스가 없다.

계속 나누고 합친다.

n log n 인 이유?

배열의 길이가 32라면? 5번 분할(32→16→8→4→2→1)

배열의 길이가 8이라면? 3번 분할(8→4→2→1)

이것이 log n.

배열의 길이가 2배가 되면 분할 횟수는 한번 늘어남.

그러면 앞에 n은 어디서 나오나?

합병할때 (merge함수) 비교하는 것이 O(n)이다.

결국 각각에 대해 O(n) 비교가 수행된다. 합병 알고리즘 자체는 O(n)의 시간복잡도를 가진다.

배열 항목이 천개라면 비교를 천번 한다.

따라서 종합적으로 O(n log n)이 되는 것이다.

O(n log n)은 정렬 알고리즘에서는 사실상 최선이다.

예외 케이스를 제외하고서는. 그러니 데이터에 구애받지 않으면 정렬 알고리즘의 최선이다.

최선, 최악, 평균 모두 O(n log n)이다.

공간 복잡도는 배열이 클수록 메모리에 더 많은 배열을 저장해야 한다.

공간을 많이 사용해야 한다. 그 점이 대가이다.

즉 공간복잡도를 더 쓰면서 시간복잡도를 줄인것이다.