분할정복

분할정복은 복잡하고 어려운 문제를 덜 복잡하고 쉬운 여러 문제들로 쪼개어 푸는 방법입니다.
가령 대량의 데이터를 정렬하고 싶을 때 분할정렬을 사용할 수 있습니다. 대량의 데이터를 작은 데이터들로 쪼개고 쪼개 한 두개의 데이터들을 비교하여 그 것을 차례대로 조합해가는 방법입니다.
분할정렬을 자바스크립트로 구현한 코드는 다음과 같습니다.

//병합정렬을 재귀함수로 구현합니다. 그 이유는 임의의 크기의 병합정렬을 리스트의 크기가 1이 될때까지 반으로 쪼개고 오름차순으로 병합을 할 것이기 때문입니다.
//탈출조건 : array의 길이가 1일 때 해당 array를 리턴합니다.
//else : 분할된 array들에 대하여 오름차순으로 병합한 array를 리턴합니다.
function mergeSort(array) {
    if(array.length===1){
        return array;
    }
    let leftArray=array.slice(0,parseInt(array.length/2));
    let rightArray=array.slice(parseInt(array.length/2));
    return merge(mergeSort(leftArray),mergeSort(rightArray));
}

// merge함수는 반복방법에서의 리스트 병합 예시 코드를 이용했습니다.
function merge(sea, fresh){
	const result = [];
    
    while(!(sea.length===0&&fresh.length===0)){
    	
        if(sea.length===0||fresh.length===0){
        	if(sea.length===0){
            	result.push(fresh[0]);
                fresh.shift();
            }else{
            	result.push(sea[0]);
                sea.shift();
            }
		}else{
        	if(sea[0]<=fresh[0]){
        		result.push(sea[0]);
            	sea.shift();
        	}else{
        		result.push(fresh[0]);
            	fresh.shift();
        	}
        }
	}
    return result;
}

위 분할정렬은 분할하기 위해서 반으로 쪼개는 과정이 시간복잡도가 logn이고 각 쪼개진 것들에 대하여 병합하는 과정이 N으로 총 시간복잡도가 nlogn으로 선택정렬의 시간복잡도 n^2보다 효율적입니다.

참고자료
1. 한 권으로 그리는 컴퓨터 과학 로드맵, 지은이 : 블라드스톤 페헤이라 필루 옮긴이 : 박연오 92P-98P
2.병합함수