[자료구조와 알고리즘] 유데미 강의 "JavaScript 알고리즘 & 자료구조 마스터클래스" 정리(섹션 15: 합병 정렬)

섹션 15: 합병 정렬

1948 폰 노이만이 최초로 작성하였다. 분할, 정렬, 합병 조합으로 정렬한다. 아래는 재귀함수를 이용한 코드이다.

function merge(arr1, arr2) {
    const 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;
}

// console.log(
//     merge([1, 10, 50], [2, 14, 99, 100])
// );

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);
}

console.log(mergeSort([76, 24, 73, 10]));

 

Big O

버블, 삽입, 선택 정렬 대비-평균적으로-훨씬 유리한 시간 복잡도를 가지지만 공간 복잡도는 불리하다. 

Algorithm	Time Complexity (Best)	Time Complexity (Average)	Time Complexity (Worst)	Space Complexity
Merge Sort	O(n log n)	O(n log n)	O(n log n)	O(n)