합병 정렬

합병 정렬은
입력받은 배열을
1자리가 될 때까지 나눈 뒤 정렬하며 합치는 알고리즘이다

두 배열을 합쳐주는 함수 merge
배열을 둘로 나누고 값을 반환할 함수 mergeSort
정렬할 배열은 [5,4,3,2,1]로 했을 때를 간단하게 그려보았습니다

그림과 같이 좌우로 절반을 나누어 1자리가 될 때 까지 실행한뒤
1자리가 되면 좌우로 나눴던 배열을 비교하여 정렬 후 합치게 된다

이번엔 코드를 보자

먼저 두 배열을 합치는 merge 함수이다

function merge(arr1,arr2){
	const result = []; // 정렬한 배열
    let i = 0;
    let j = 0;
    
    while(i< arr1.length && j < arr2.length){
    	if(arr2[j] > arr1[i]){
        	result.push(arr1[i]);
          	i++;
        }
      	else{
        	result.push(arr2[j]);
          	j++;
        }
    }
  	
  	// 한 쪽이 빨리 끝난다면 나머지들 push
  	while(i < arr1.length){
    	result.push(arr[i]);
      	i++;
    }
  
  	while(j < arr2.length){
    	result.push(arr[j]);
      	j++;
    
}

mergeSort함수

function mergeSort(arr){
	if(arr.length <= 1) return arr;
  	const mid = Math.floor(arr.length / 2);
    const left = mergeSort(arr.slice(0,mid));
  	const right = mergeSort(arr.slice(mid));
  
  	return merge(left,right)
}

정렬할 배열 arr를 좌우로 나누어 한 자리가 될 때 까지 재귀를 통해 반복한다
한 자리 수가 되면 left,right값이 정해지기 떄문에 merge(left,right) 실행하여 얻은 정렬된 배열을 반환한다
이를 반복하여 최종적으로 정렬이 된 배열을 반환한다