기본 정렬 알고리즘 - 병합정렬(Merge Sort)

기본적인 정렬 알고리즘에는 삽입, 선택, 버블, 퀵, 병합정렬 등이 있습니다.

이 중에서 병합정렬에 대해서 알아보도록 하겠습니다.

 

병합정렬(Merge Sort)의 특징

• 병합정렬의 핵심 아이디어는 "일단 반으로 나누고 나중에 합쳐서 정렬한다." 입니다.

• 시간 복잡도 O(N * log N)

• 퀵 정렬과 다르게 최악의 경우에도 O(N * logN)을 보장합니다.

코드

/**
 * 병합정렬의 핵심 아이디어,
 * `일단 반으로 나누고 나중에 합쳐서 정렬한다.`
 * 
 * 퀵정렬과 다르게 항상 속도는 O(N * logN)이 된다.
 * 퀵정렬과 동일하게 분할정복법과 재귀함수를 사용한다.
 */

function solution(arr)
{
    let sortedArr = [];
    mergeSort(arr, 0, arr.length - 1, sortedArr);
    return arr;
}

/**
 * 나뉘어진 함수를 합치는 함수
 * 
 * @param {*} arr 배열
 * @param {*} m 배열 시작점
 * @param {*} middle 배열 중간점
 * @param {*} n 배열 끝점
 */
function merge(arr, m, middle, n, sortedArr)
{
    let i = m;              // 쪼갠 배열의 왼쪽 배열의 시작점
    let j = middle + 1;     // 쪼갠 배열의 오른쪽 배열의 시작점
    let k = m;              // 정렬된 배열의 시작점

    // 작은 순서대로 배열에 삽입
    while (i <= middle && j <= n)
    {
        if (arr[i] <= arr[j])
        {
            sortedArr[k] = arr[i];
            i++;
        }
        else
        {
            sortedArr[k] = arr[j];
            j++;
        }

        k++;
    }

    // i 또는 j가 먼저 끝났을 경우 남은 데이터 삽입
    if (i > middle)
    {
        for (let t = j; t <= n; t++)
        {
            sortedArr[k] = arr[t];
            k++;
        }
    }
    else
    {
        for (let t = i; t <= middle; t++)
        {
            sortedArr[k] = arr[t];
            k++;
        }
    }

    // 정렬된 배열을 삽입
    for (let t = m; t <= n; t++)
        arr[t] = sortedArr[t];
}

/**
 * 반으로 나누는 함수
 * 
 * @param {*} arr 배열
 * @param {*} m 배열 시작점
 * @param {*} n 배열 끝점
 */
function mergeSort(arr, m, n, sortedArr)
{
    // 크기가 1보다 큰 경우만 처리
    if (m < n)
    {
        let middle = parseInt((m + n) / 2);
        mergeSort(arr, m, middle, sortedArr);
        mergeSort(arr, middle + 1, n, sortedArr);
        merge(arr, m, middle, n, sortedArr);
    }
}

console.log(solution([7, 6, 5, 8, 3, 5, 9, 1]));
console.log(solution([1, 9, 2, 7, 3]));
console.log(solution([1, 10, 5, 8, 7, 6, 4, 2, 3, 9]));
console.log(solution([5, 2, 3, 4, 1]));
console.log(solution([5, 2, 3, 1, 4]));

 

참조

https://www.youtube.com/watch?v=ctkuGoJPmAE&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz&index=8