Merge Sort (병합 정렬)

병합 정렬이란 ?

병합 정렬 (Merge Sort) 은 정렬 알고리즘 중 하나로 분할 정복 알고리즘을 사용한다. 즉 문제를 작은 2개의 문제로 분리하여 분리 된 각각의 작은 문제를 해결하여 해결한 결과를 가지고 원래의 문제를 해결하는 방식이다. 

보통의 분할 정복 방법은 순환 호출 (재귀 함수)를 이용하여 구연하게 된다.

 

병합 정렬 과정

병합 정렬은 다음과 같은 과정으로 수행 된다.

1. 입력 받은 List를 2개의 List로 나눈다. 이때 나누는 횟수는 나누어진 List가 더이상 나누어 질 수 없을때 까지 반복한다. 
2. 더 이상 나누어 질 수 없게 된 경우 2개의 List의 각 요소를 비교하여 (큰값, 작은값) 을 새로운 리스트에 옮긴다.
3. 만약 위의 과정에서 2개의 List 중 하나라도 요소가 모두 옮겨져 요소가 없을 경우 남은 List의 모든 요소를 새로운 리스트에 옮긴다. (이때 남은 List의 요소는 모두 정렬 된 상태이다)

출처 : https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

 

위의 과정을 반복하게 되면 병합 정렬이 이루어지며, 동작 과정을 통해 알 수 있듯 순환 호출을 통해 List가 더이상 나누어 질 수 없을때 까지 호출하며 더이상 나누어 질 수 없을 때 Return 을 통해 정렬 된 List를 반환 하는 과정을 통해 손쉽게 구현이 가능하다.

입력받은 List를 계속 반으로 나누기 때문에 분할 단계에서는 비교 연산과 이동 연산이 수행되지 않으며, 병합하는 단계에서는 최대 N번의 연산 ( 더이상 나누어 질 수 없을 때 까지 분활하여 N개 만큼 비교하여 새로운 배열에 추가하기 때문 ) 을 수행한다.

따라서 입력받는 List의 크기가 클 수록 시간 복잡도가 효율적으로 줄어들게 된다. (입력받은 List를 2개로 나누어 처리하기 때문) nlog n 의 시간이 소요 된다.

출처 : https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

 

소스 코드 (JavaScript)

"use strict";

debugger;

var nList = [3,1,7,6,4,5,9,2,8];

// 분할 단계
// 재귀를 통해 List의 크기가 1일 때 까지 반복
function mergeSort(arr){
    if(arr.length === 1) return arr;
    else{
        var mid = parseInt(arr.length / 2, 10);
        var left = arr.slice(0, mid);
        var right = arr.slice(mid);
        return merge(mergeSort(left), mergeSort(right)); 
    }
}

// 입력받은 2개의 List의 요소의 가장 앞의 값을 비교한다.
// 비교한 값의 특정 요소를 새로운 List에 추가하며
// 입력받은 List 중 하나라고 요소가 모두 새로운 배열에 추가 된 경우
// 남은 List의 모든 요소를 새로운 배열에 추가한다.
function merge(left, right){
    var result = [];
    while(left.length >= 1 && right.length >= 1){
        if(left[0] > right[0]){
            result.push(right.shift());
        }
        else{
            result.push(left.shift());
        }
    }
    while(left.length >= 1){
        result.push(left.shift());
    }
    while(right.length >= 1){
        result.push(right.shift());
    }
    return result;
}

var nList1 = mergeSort(nList);

console.log(nList1);