分割征服

//병합정렬을 재귀함수로 구현합니다. 그 이유는 임의의 크기의 병합정렬을 리스트의 크기가 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;
}