복잡하지만 효율적인 병합 정렬, Javascript

문제

정수를 요소로 갖는 배열을 입력받아 오름차순으로 정렬하여 리턴해야 합니다.

주의 사항

• 병합 정렬을 구현해야 합니다.
• arr.sort 사용은 금지됩니다.
• 입력으로 주어진 배열은 중첩되지 않은 1차원 배열입니다.

입출력 예시

let output = mergeSort([3, 1, 21]);
console.log(output); // --> [1, 3, 21]

풀이

const mergeSort = function (arr) {
	if(arr.length < 2){
    	return arr;
    }
    
    let middle = Math.floor(arr.length / 2);
    let left = arr.slice(0, middle);
    let right = arr.slice(middle);
    
    return mergeFunction(mergeSort(left), mergeSort(right));
    
    function mergeFunction(left, right){
    	let result = [];
        let leftIdx = 0;
        let rightIdx = 0;
        
        while(leftIdx < left.length && rightIdx < right.length){
        	if(left[leftIdx] < right[rightIdx]){
            	result.push(left[leftIdx]);
                leftIdx++;
            } else {
            	result.push(right[rightIdx]);
                rightIdx++;
            }
        }
        return result.concat(left.slice(leftIdx), right.slice(rightIdx));
    }
};

기존 정렬보다 많이 어려웠다. 다양한 방법이 있겠지만 왜 병합 정렬을 사용하는가 검색해본 결과 복잡하지만 시간 복잡도에서 가장 우위에 있는 방법이기 때문이다. 한 마디로 효율적이다.

병합 정렬은 분할, 정복, 결합 으로 이루어진다. 쪼개고, 비교하고, 결합해서 결과값을 반환한다.

병합 정렬에 대한 장,단점

• 장점: 다른 정렬 방법보다 효율적이다.
• 단점: function에 대한 코드 작성, 이해가 불가능하면 접근 조차 힘들다.

결론.. 경험하는 느낌으로 문제를 풀었지 스스로 생각해서 풀기에 mergeFunction 구현도 힘들었다. 코드를 보고 어떤 방식으로 작동하는지 알겠지만 코드를 보기 전에는 풀이 접근 조차 힘든 문제였다.