병합 정렬 ( merge sort )

합병 정렬 ( merge sort )

합병 정렬이란?

합병 정렬 또는 병합 정렬(merge sort)은 O(n log n) 비교 기반 정렬 알고리즘이다. 일반적인 방법으로 구현했을 때 이 정렬은 안정 정렬에 속하며, 분할 정복 알고리즘의 하나이다. 존 폰 노이만이 1945년에 개발했다.

합병 정렬은 다음과 같이 작동한다.

1. 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는
2. 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
3. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
4. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.

코드와 설명

const mergeSort = arr => {
    if ( arr.length < 2 ) return arr; // 배열의 길이가 1개일 때 배열을 리턴
    const middle = parseInt(arr.length/2); // 배열의 중간지점을 잡음
    const left = arr.slice(0, middle); // 0부터 중간까지
    const right = arr.slice(middle, arr.length); // 중간부터 끝까지
    return merge(mergeSort(left), mergeSort(right)); // merge라는 정렬해주는 함수에 인자로 보내줌
}

const merge = (left, right) => {
    let result = []; // 합병 결과 리턴값
    while ( left.length && right.length ) {
        left[0] > right[0] ? result.push(right.shift()) : result.push(left.shift()); // left, right 둘중 하나의 원소가 없을 때 까지 대소 비교 후 result 에 삽입
    }
    while ( left.length ) {
        result.push(left.shift()); // left의 남은 원소 삽입
    }
    while ( right.length ) {
        result.push(right.shift()); // right의 남은 원소 삽입
    }
    return result; // 리턴
}

console.log(mergeSort([3, 2, 1]))

우선 mergeSort라는 함수로 배열을 받으면, 배열의 길이가 1이될 때까지 반씩 쪼갬과 동시에 쪼갠 배열을 merge라는 함수에 넣어 순서대로 정렬한 뒤에 다시 합쳐준다.

사실 짜고도 완벽하게 정렬 과정이 이해가 안된다. 조금더 봐야할 것 같음ㅜ

// 추가 내용 : 직접 코드 진행 과정을 써보니까 이해가 되었음

mergeSort([3,2,1]) 을 기준으로 과정을 나열해 보면

mergeSort([3,2,1])

merge(mergeSort([3]), mergeSort([2,1])) // left, right 로 나뉘어져 리턴

merge([3], mergeSort([2,1])) // left 값, 즉 [3]은 배열의 길이가 1이므로 배열 자체를 리턴

merge([3], merge([2],[1])) // right값은 다시한번 left값 [2], right값 [1] 로 나뉘어짐

merge([3], [1,2]) // merge 함수에 의해 merge([2],[1]) 이 [1,2]로 리턴

[1,2,3] // merge 함수에 의해 merge([3], [1,2]) 가 [1,2,3]으로 리턴

위와 같이 정렬이 된다.

쉽다 !