Merge sort에 관하여..

merge sort

merge sort는 quick sort 와 비슷하게 분할 정보 알고리즘의 하나이며
quick sort는 피벗의 값에 따라 편향되게 분할 될 수 있지만 merge sort는 안전하게
반절씩나눈다는 점에서 최악의 경우에도 O(nlogn)의 시간 복잡도를 보장함.

병합 정렬은 in place 알고리즘이 아니기 때문에 별도의 메모리 공간이 필요.
만약에 정렬할 데이터의 양이 많은 경우에는 그만큼 이동 횟수가 많아지므로 시간적인 낭비도 많아지게 됨.

<merge sort javascript 구현>

mergeSort(arr): 반으로 나누어 주는 함수
merge(left,right): 반으로 나누어준 함수를 갖고 정렬해 새로운 배열로 만들어주는 함수
(이 과정에서 새로운 배열로 만들어 주기 때문에 메모리가 입력 배열의 크기만큼 필요)

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 sortedArr = [];
  while (left.length && right.length) {
  	if (left[0] >= right[0]) {
    	sortedArr.push(right.shift());
    } else {
    	sortedArr.push(left.shift());
    }
  }
	return [...sortedArr, ...left, ...right];
}

cf) slice 메소드를 이용해 분할하였고, shift 메소드를 사용해 머지하는 형태
여기서 shift()메소드는 첫 번째 요소를 제거하고, 제거된 요소를 반환.