[알고리즘] 정렬 알고리즘(2) by javascript - Merge(병합/합병)

* 정렬의 동작 원리는 아래 사이트를 통해 보면 이해하기 쉽다.

https://visualgo.net/en/sorting

Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix) - VisuAlgo

---

1. 병합 정렬 (Merge Sort)

합병 정렬이라고도 하는 병합 정렬은 데이터들을 잘게 쪼갠 다음에 하나로 합치는 과정에서 정렬하는 알고리즘이다.

(병합 정렬은 정렬 알고리즘이면서 분할 정복 알고리즘에도 속한다.)

 

시간 복잡도는 O(n logn)으로 앞 서 작성했던 기본 정렬 알고리즘과 다르게 매우 준수한 성능을 자랑한다.

하지만 구현 난이도 역시 있는 편이라 이번 기회에 익혀보자.

 

▷ 병합 정렬(Merge Sort) 알고리즘 구현

const merge = (left, right) => {
    const result = [];
    while(left.length && right.length){
        result.push(left[0] <= right[0] ? left.shift() : right.shift());
    }
    return [...result, ...left, ...right];
}

const mergeSort = (arr) => {
    if(arr.length < 2) return arr;
    let mid = Math.floor(arr.length / 2);
    let left = arr.slice(0, mid);
    let right = arr.slice(mid);
    return merge(mergeSort(left), mergeSort(right));
}

mergeSort([11, 48, 17, 49, 19, 22, 10, 29, 47, -1, 47, 3, 30, 7, 14, 24]);
// [-1, 3, 7, 10, 11, 14, 17, 19, 22, 24, 29, 30, 47, 47, 48, 49]

 

동작 원리는 본문 상단에 있는 사이트를 가서 Merge Sort를 틀어놓고 코드와 비교해보면서 보면 이해하기 쉽다.

 

재귀 함수를 사용하는 거라 최종적으로는 배열의 길이가 1이 될 때까지 쪼개진 다음 하나씩 합쳐가면서 정렬을 시켜주는 원리이다. 그렇게 정렬을 시켜주면서 하나의 배열로 반환시켜준다.

---

참고 : 위키백과 - 합병_정렬

합병 정렬 - 위키백과, 우리 모두의 백과사전