병합 정렬

병합 정렬은 배열을 두개로 나누고 나눈 배열끼리 비교해서 작은 값을 먼저 넣으며 정렬하는 방식입니다. 이 과정에 한 번으로만 쪼개면 제대로된 정렬이 될리 없으므로 재귀를 이용해서 나눈 배열을 또 나누고 나누어 각 요소가 1개일 경우까지 쪼갠다음 비교해서 작은것 부터 순차적으로 넣으면됩니다. 병합 정렬의 시간 복잡도는 O(nlogn)입니다.

다음과 같은 배열이 있으면, 두 개의 배열로 나눕니다.

두 개의 배열로 나눈 다음에 나눈 배열의 첫 번째 요소끼리 비교해서 작은 요소를 먼저 넣고 인덱스를 1증가시켜 큰 요소를 넣으면 됩니다.이대로 넣으면 [3, 9, 2, 4, 5, 7, 1, 8]로 정렬이 안되겠죠? 이를 위해 4개로 나눈것에서 다시 오른쪽 왼쪽으로 나누고... 요소 갯수가 1인 배열이 나올때 까지 반복합니다. 그리고 병합을 하며 정렬하면 순서대로 정렬이 되게 되는 것이 병합 정렬의 원리입니다.

병합 정렬 구현

export const mergeSort = arr => {
    if (arr.length < 2) {
        return arr;
    }
    
    //반으로 나누는 피벗
    const pivot = Math.floor(arr.length / 2);
    //나눈 왼쪽
    const left = arr.slice(0, pivot);
    //나눈 오른쪽
    const right = arr.slice(pivot, arr.length);

    return merge(mergeSort(left), mergeSort(right));
};

//병합을 하는 함수
const merge = (left, right) => {
    const result = [];

    while (left.length && right.length) {
        //왼쪽 오른쪽 배열의 첫 원소끼리 비교합니다.
        if (left[0] <= right[0]) {
            //오른쪽이 더 크면 왼쪽의 요소부터 result에 삽입
            result.push(left.shift());
        }
        else {
            //왼쪽이 더 크면 오른쪽 요소부터 result에 삽입
            result.push(right.shift());
        }
    }
    
    //배열 크기가 어느 한 쪽이 남는다면, 남은 것들을 result에 삽입
    while (left.length) {
        result.push(left.shift());
    }

    while (right.length) {
        result.push(right.shift());
    }

    return result;
};