정렬 (Sort) - 병합정렬

병합정렬이란

병합정렬(Merge Sort)은 분할 정복(Divide and Conquer) 알고리즘의 일종으로, 배열을 반으로 나누어 각각을 정렬한 후 합치는 과정을 반복하여 정렬을 완료하는 알고리즘.

• 병합정렬은 안정 정렬로, 같은 값의 원소들 간의 순서가 바뀌지 않음.

병합정렬 요약

특징	분할 정복 알고리즘 병합정렬은 분할 정복(Divide and Conquer) 알고리즘의 일종 문제를 더 작은 부분 문제로 나누고 각각을 해결한 후 합쳐서 최종 해결책을 만드는 방식. 재귀적 접근 병합정렬은 재귀적으로 배열을 반으로 나누어 더 이상 나눌 수 없을 때까지 나누고, 나눈 배열을 병합하여 정렬 외부 정렬 가능 병합정렬은 외부 정렬(external sorting)에 적합. 대규모 데이터를 정렬할 때, 메모리에 모두 적재할 수 없는 경우에 사용될 수 있음. 균등한 성능 다른 정렬 알고리즘과 달리, 데이터의 초기 정렬 상태에 상관없이 항상 O(n log n)의 성능을 보장. 이는 최악의 경우에도 일관된 성능을 제공한다는 의미.
장점	안정 정렬 병합정렬은 안정 정렬(stable sort)로, 동일한 값의 원소들이 입력 순서대로 유지. 이는 데이터의 순서를 유지해야 하는 상황에서 중요한 특징. O(n log n) 시간복잡도 최선, 평균, 최악의 경우 모두 O(n log n)의 시간복잡도를 가짐. 이는 매우 효율적인 시간복잡도.
단점	추가 메모리 공간 필요 병합정렬은 배열을 나누고 병합하는 과정에서 추가 메모리 공간이 필요. 이 추가 공간의 복잡도는 O(n).
시간복잡도	최선, 평균, 최악 : O(n log n)
공간복잡도	O(n)

 

자바스크립트 예시

// 병합 함수: 두 개의 정렬된 배열을 하나의 정렬된 배열로 합칩니다.
function merge(left, right) {
    let resultArray = [], leftIndex = 0, rightIndex = 0;

    // 두 배열의 각 요소를 비교하여 작은 값을 결과 배열에 추가합니다.
    while (leftIndex < left.length && rightIndex < right.length) {
        if (left[leftIndex] < right[rightIndex]) {
            resultArray.push(left[leftIndex]);
            leftIndex++;
        } else {
            resultArray.push(right[rightIndex]);
            rightIndex++;
        }
    }

    // 왼쪽 배열에 남은 요소를 결과 배열에 추가합니다.
    while (leftIndex < left.length) {
        resultArray.push(left[leftIndex]);
        leftIndex++;
    }

    // 오른쪽 배열에 남은 요소를 결과 배열에 추가합니다.
    while (rightIndex < right.length) {
        resultArray.push(right[rightIndex]);
        rightIndex++;
    }

    return resultArray;
}

// 병합 정렬 함수: 배열을 반으로 나누어 재귀적으로 정렬합니다.
function mergeSort(array) {
    if (array.length <= 1) {
        return array;
    }

    const middleIndex = Math.floor(array.length / 2);
    const leftArray = array.slice(0, middleIndex);
    const rightArray = array.slice(middleIndex);

    return merge(mergeSort(leftArray), mergeSort(rightArray));
}

// 테스트
const array = [34, 7, 23, 32, 5, 62];
const sortedArray = mergeSort(array);
console.log(sortedArray);