소개

1945년에 컴퓨터 과학자이자 수학자인 존 폰 노이만이 소개했다.(많이 들어 봤지만 현재 시점에서 찾아보니 개쩌는 사람이었다..)

• 이름 그대로 merge 하고 sort의 조합이다.
• 배열을 더 작은 배열로 나누는 방식이다. 0개 혹은 1개의 요소가 남을때까지 나누고 합병하여 정렬된 배열을 만든다.

1. 배열을 반으로 쪼갠다.
2. 요소가 0개 혹은 1개가 남을때까지 쪼갠다.
3. 다 쪼개 졌으면, 다시 옆에 있는 요소와 비교해서 정렬된 배열로 합병한다.
4. 반복.

합병 정렬 구현

배열 합병 - 구현하기

두 배열이 있고 두 배열 모두 정렬이 되어 있다고 가정했을때, 합병을 구현해보겠습니다.

function merge(arr1, arr2){
    let result = [];
    let i = 0;
    let j = 0;
    
    // arr1 과 arr2를 요소 하나씩 비교해나가는 것
    // 작은 요소를 하나씩 result에 push
    
    while(i < arr1.length && j < arr2.length){
        if(arr2[j] > arr1[i]){
            result.push(arr1[i]);
            i++;
        } else {
            result.push(arr2[j])
            j++;
        }
    }
    
    // 한쪽 배열의 비교가 끝났을때 나머지 요소들을 다 집어넣음.
    while(i < arr1.length) {
        result.push(arr1[i])
        i++;
    }
    while(j < arr2.length) {
        result.push(arr2[j])
        j++;
    }
    return result;
}

합병 정렬 - 구현하기

위에서 배열을 합병하는 코드를 구현했습니다.
이제는 정렬되지 않은 배열을 작은 요소로 쪼깨고 합병 정렬을 수행하는 코드 작성해보겠습니다.

• 빈배열이되거나 요소를 하나만 가질때까지 배열을 반으로 쪼갠다.
• 작고 정렬된 배열을 가지면, 다른 정렬된 배열들과 함께 배열들을 합친다.
• 배열이 다시 모두 합쳐지면, 배열을 return 한다.

function merge(arr1, arr2){
    let result = [];
    let i = 0;
    let j = 0;
    while(i < arr1.length && j < arr2.length){
        if(arr2[j] > arr1[i]){
            result.push(arr1[i]);
            i++;
        } else {
            result.push(arr2[j])
            j++;
        }
    }
    while(i < arr1.length) {
        result.push(arr1[i])
        i++;
    }
    while(j < arr2.length) {
        result.push(arr2[j])
        j++;
    }
    return result;
}

function mergeSort(arr){
    if(arr.length <= 1) return arr;
    let mid = Math.floor(arr.length/2);
    // 쪼개진 좌측 배열을 재귀를 통해서 계속 쪼갠다.
    // 요소가 0개 혹은 1개이면 다른 요소와 정렬되면서 합병되게 된다.
    let left = mergeSort(arr.slice(0,mid));
    let right = mergeSort(arr.slice(mid));
    return merge(left, sright);
}

합병 정렬의 Big O

시간 복잡도 O(n log n)
공간 복잡도 O(n)

배열의 요소가 2배씩 증가함에 따라서 쪼개는 횟수가 1회씩 추가되게 됩니다. 그래서 O(log n) 의 시간 복잡도가 발생하고
합병을 할때 두 배열간 요소를 비요할때 O(n) 이라는 시간 복잡도가 필요하게 됩니다. 그래서 총 시간 복잡도는 O(n log n)이 됩니다.