병합정렬

• 병합 정렬은 데이터들을 쪼갠 다음 하나로 합치면서 정렬하는 방법이다.

• Divde and Conquer 기법

  • 분할 (Divide) : 배열을 2개의 배열로 재귀를 통해 계속 분할한다.

• 정복 (Conquer) : 분할된 배열을 정렬

• 결합 (Combine) : 정렬된 부분을 다시 합친다.

특징

• 시간 복잡도
  - 평균의 경우: O(nlog₂n)

  • 최악의 경우: O(nlog₂n)

• 병합정렬은 최선의 경우에도, 최악의 경우에도 같은 시간이 소요되기 떄문에 데이터 분포에 영향을 덜 받는다

• 별도의 메모리 공간이 필요하다, 정렬한 데이터 양에 많은 경우 이동횟수가 많아저 시간적인 낭비도 많아지게 된다

• stable 정렬

구현

function mergeSort (array) { // 배열을 분할하는 함수
	if (array.length < 2) {
		return array;
	}

  	const mid = Math.floor(array.length / 2);
	const left = array.slice(0, mid);
	const right = array.slice(mid);
  
	return merge(mergeSort(left), mergeSort(right)); 
}
  function merge (left, right) { // 분할된 함수를 받아옴, 

    const resultArray = [];
	let leftIndex = 0;
	let rightIndex = 0;
	
    while (leftIndex < left.length && rightIndex < right.length) { 
		if (left[leftIndex] < right[rightIndex]) { // 값 비교
			resultArray.push(left[leftIndex]); // 작은 값을 먼저 집어넣음
			leftIndex++;
		}
      	else {
			resultArray.push(right[rightIndex]);
			rightIndex++;
		}
	}
	return resultArray.concat(left.slice(leftIndex),right.slice(rightIndex));
}