[Sort] Merge Sort

Merge Sort

---

배열을 두 부분으로 쪼갠 뒤, 각 배열의 첫번째 요소를 비교해 작은 원소부터 새로운 배열에 넣으며 정렬한다.
배열의 길이가 길 경우, 한번에 정렬하기 어렵기 때문에 재귀적으로 배열을 잘게 자르고 정렬하는 것을 반복한다.
문제를 작은 2개의 문제로 분리한 후, 해결하고 다시 합치는 분할 정복 방법을 사용한다.
시간복잡도는 O(nlog(n))

 

구현한 코드

function mergeSort (array) {
  // array에 원소 1개만 들어있을때
  if (array.length < 2) {
    return array;
  }

  let mid = Math.floor(array.length / 2); // 쪼개질 기준점
  let front = array.slice(0, mid); // 쪼개진 앞부분
  let back = array.slice(mid); // 쪼개진 뒷부분

  function recursion (front, back) {
    // front, back의 첫번째를 비교
    // 비교하고 정렬한 뒤 이걸 합친 배열이 반환되어야 함

    let result = []; // 여기다가 작은 원소부터 넣어줄 것

    while (front.length && back.length) {
      if (front[0] <= back[0]) {
        // 앞쪽 배열의 첫번째 요소가 더 작을때
        result.push(front.shift());
      } else {
        // 뒤쪽 배열의 첫번째 요소가 더 작을때
        result.push(back.shift());
      }
    }

    // 원소가 남았을 경우
    while (front.length) {
      result.push(front.shift());
    }

    while (back.length) {
      result.push(back.shift());
    }

    return result;
  };

  // front, back도 모두 쪼개서 merge함수에 넣어 정렬
  return recursion(mergeSort(front), mergeSort(back));
};