JS 병합정렬 (merge sort) 하나하나 이해하기.

알고리즘 공부를 시작하고, 병합정렬을 만났다.

'병합정렬'이라는 컨셉은 이해가 되는데, js 함수에서 도대체 어떻게 되고 있는건지 이해가 안갔다.
구체적으로, 배열을 재귀적으로 나누는 것은 이해가 되었지만, 다시 겹치는 부분이 이해가 되지 않았다.

그래서 오랜만에 펜을 들고 그려보기로 했다.

가끔 이해안가는 부분은 손으로 쓰면 이해가 되더라.

var mergeSort = function(array) {
  if (array.length < 2) return array; // 원소가 하나일 때는 그대로 내보냅니다.
  var pivot = Math.floor(array.length / 2); // 대략 반으로 쪼개는 코드
  var left = array.slice(0, pivot); // 쪼갠 왼쪽
  var right = array.slice(pivot, array.length); // 쪼갠 오른쪽
  return merge(mergeSort(left), mergeSort(right)); // 재귀적으로 쪼개고 합칩니다.
}
function merge(left, right) {
  var result = [];
  while (left.length && right.length) {
    if (left[0] <= right[0]) { // 두 배열의 첫 원소를 비교하여
      result.push(left.shift()); // 더 작은 수를 결과에 넣어줍니다.
    } else {
      result.push(right.shift()); // 오른쪽도 마찬가지
    }
  }
  while (left.length) result.push(left.shift()); // 어느 한 배열이 더 많이 남았다면 나머지를 다 넣어줍니다.
  while (right.length) result.push(right.shift()); // 오른쪽도 마찬가지
  result.forEach(e=>console.log("result"+ e))
  return result;
};

let answer =mergeSort([5,2,4,7,6,1,3,8]); // [1, 2, 3, 4, 5, 6, 7, 8]

console.log(answer);

#그림

내려가면서는 검정색 선과 검정 함수만 보고
마지막 빨강색 return값을 받으면 빨강색라인으로만 올라오는 건데
보기좋게 그리진 못했다.
정렬 공부를 다 끝내고 다 보기좋게 만들어봐야겠다 :)