병합 정렬(Merge Sort)

📌 병합 정렬

병합 정렬은 분할 정복 (Divide and Conquer) 기법과 재귀 알고리즘을 이용해서 정렬하는 알고리즘이다. 주어진 배열을 원소가 하나 밖에 남지 않을 때까지 계속 둘로 쪼갠 후에 다시 크기 순으로 재배열 하면서 원래 크기의 배열로 합치는 과정을 거친다.

 

👀 Example

function merge(arr1, arr2) {
    let results = [];
    let i = 0;
    let j = 0;
    while(i < arr1.length && j < arr2.length) {
        if(arr2[j] > arr1[i]) {
            results.push(arr1[i])
            i++;
        }else {
            results.push(arr2[j])
            j++;
        }
    }
    while(i < arr1.length) {
        results.push(arr1[i])
        i++;
    }
    while(j < arr2.length) {
        results.push(arr2[j])
        j++;
    }

    return results;
}

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

mergeSort([1, 10, 50, 2, 14, 99, 100])

mergeSort(arr) : 주어진 배열을 반으로 나누어 주는 함수

merge(arr1, arr2) : 반으로 나눈 배열을 정렬해 새로운 배열로 만들어주는 함수

 

merge함수를 조금 더 간략화 하면 아래와 같이 수정할 수 있다.

function merge(arr1, arr2) { 
	const result = [];
	while (arr1.length !== 0 && arr2.length !== 0) {
		arr1[0] <= arr2[0] ? result.push(arr1.shift()) : result.push(arr2.shift());	
	}
	return [...result, ...arr1, ...arr2];
}