합병정렬

병합정렬도 정렬 방법 중 하나이다. 방법은 주어진 배열을 반으로 나누어 크기 순으로 새로운 배열에 넣는 방식이다.

 

이 방식은 앞의 버블정렬, 삽입정렬, 선택정렬과 다르게 시간복잡도가 O(nlogn)이다. 그래서 앞의 세가지보다 더 사용하기 좋지만, 최악의 경우를 고려한다면 퀵정렬이 조금 더 앞선다고 한다.

 

function mergeSort(array) {
    if(array.length < 2) return array;

    var pivot = Math.floor(array.length / 2);
    
    var left_arr = array.slice(0, pivot);
    var right_arr = array.slice(pivot);

    return merge(mergeSort(left_arr), mergeSort(right_arr));
}

function merge(left, right) {
    var result = [];
    while(left.length && right.length){
        if(left[0] < right[0]) result.push(left.shift());
        else result.push(right.shift());
    }

    while (left.length) result.push(left.shift());
    while (right.length) result.push(right.shift());
    return result;
}

console.log(mergeSort([1,2,7,2,5,3,8,4,3,2,11]));
/*
[
   1, 2, 2, 2, 3,
   3, 4, 5, 7, 8,
  11
]
*/