병합 정렬

병합 정렬은 분할, 정렬, 합치기 이 세 가지를 수행 하면서 배열을 정렬하는 알고리즘이다.

기존에 퀵 정렬은 최악의 상황을 제외한 경우에서 매우 빠른 속도를 제공하지만 불안정 정렬이고

최악의 경우에는 n^2이라는 시간 복잡도를 가진다.

하지만 병합 정렬은 어떠한 상황에서도 O(NlogN)이라는 이상적인 속도와 안정 정렬을 제공해주는 알고리즘이다.

1.분할

const arr = [5,3,7,4,8,9,1,2,6];

이렇게 정렬 되지 않은 배열을 병합 정렬로 정렬 하고자 할때

더 이상 쪼개지지 않을 때 까지 분할을 해준다.

[5],[3],[7],[4],[8],[1],[2],[6]

마지막 까지 분리해 줬다면 앞 에서 부터 두 개씩 묶어서 정렬을 시작한다.

2.정렬+합병

[3,5],[4,7],[1,8],[2,6]

[3,4,5,7],[1,2,6,8]

[1,2,3,4,5,6,7,8];

정렬과 동시에 합병을 진행한다.

자바스크립트로의 구현

let arr = [5,3,7,4,8,9,1,2,6];

function merge_sort(left,right){
	let result = [];
	let i = 0,j = 0;
	while(left[i] || right[j]) {
		if(left[i] && right[j]) {
      		left[i] > right[j]
      		? (result.push(right[j]),j++)
      		: (result.push(left[i]),i++)
    	} else {
      		left[i] === undefined 
      		? (result.push(right[j]),j++)
      		: (result.push(left[i]),i++);
    	}
	}
	return result;
};

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

console.log(merge(arr));

merge 함수 안에 left와 right는 재귀적으로 호출하여 맨 마지막 arr.length가 1인 경우까지 쪼개지고

merge_sort 함수에 들어가게 된다 정렬과 합병 과정을 거치면서 다시 원래의 N크기 만큼의 배열로 정렬되면서 합쳐진다.

퀵 정렬은 pivot값에 따라 시간 복잡도가 달라지게 되지만 병합 정렬에서는 최소한의 크기로 쪼개고 정렬 하면서 합치기 때문에 어느 상황에서도 일정한 O(NlogN)의 시간 복잡도를 가지게 된다.