Merge Sort

• Divde and Conquer 기법으로 알고리즘 문제를 작은 것부터 정렬해가며 결과적으로 모든 데이터를 정렬하는 기법
• 시간 복잡도 : worst case - O(nlog₂n), best case - O(nlog₂n)
• in place 알고리즘이 아니기 때문에 별도의 메모리 공간이 필요하다.

const mergeSort = (arr) => {
	// arr의 길이가 1보다 작거나 같으면 그냥 arr리턴한다.
	if(arr.length <= 1) {
		return arr;
	}

	// mid, left, right 변수 생성
	let mid = Math.floor(arr.length / 2);
	let left = arr.slice(0, mid);
	let right = arr.slice(mid);

	return merge(mergeSort(left), mergeSort(right));
};

const merge = (left, right) => {
	// 배열변수 생성
	let result = [];
	// left, right 인덱스 생성
	let leftIdx = 0;
	let rightIdx = 0;

	// left, right인덱스가 left, right의 길이보다 작을때까지 무한반복
	while(leftIdx < left.length && rightIdx < right.length) {
		// leftIdx 요소가 rightIdx 요소보다 작은경우
		if(left[leftIdx] < right[rightIdx]) {
			result.push(left[leftIdx]);
			leftIdx++;
		} else {
				result.push(right[rightIdx]);
				rightIdx++;
			}
	}

	// while문까지 수행된 leftIdx, rightIdx를 잘라서 result에 붙여준다.
	return result.concat(left.slice(leftIdx), right.slice(rightIdx));
}