[Udemy 알고리즘&자료구조] 합병정렬

1. 개념

- 버블,삽입,선택정렬에 비해서 매우매우 효율적인 정렬.
- 분할, 정렬, 합병의 조합으로 이루어져있다.
    a. 분할 : 배열을 분할하여 새로운 배열을 만드는데, 배열의 요소가 1개가 될 때까지 배열을 분할한다. length가 8인 배열을 분할하면 8개의 배열이 나와야 한다.
    b. 정렬과 합병 : 이제 8개로 분할된 배열을 2개씩 합병하는데, 정렬을 시킨다. 마찬가지로 2개씩 합병된 배열을 다시 정렬하면서 4개씩 합병한다. 마지막으로 8개의 요소가 정렬된 하나의 배열로 합병한다.  
-----------------

2. 합병 알고리즘

    a. 두 정렬된 배열을 합치는 함수를 만든다.(정렬은 오름차순이든 내림차순이든 통일되어야 한다.)
    b. 정렬된 두 배열이 주어지면, 함수는 정렬된 새로운 배열을 반환해야하고, 인자로 전달된 두 배열의 모든 요소가 들어가 있어야 한다.
    c. 이 함수의 시간복잡도는 O(n+m)이다.(전달된 각 배열의 길이)

3. 합병함수 의사코드

    a. 인자로 합병할 배열 두 개를 받는다.
    b. 마지막에 반환할 빈배열을 만들고, 각각의 input array에 대해 가장 작은 값부터 시작하는 반복문을 생성한다.
    c. while문으로하며, 변수는 i와 j 두개다.
    d. 첫번째 배열의 첫 번째 요소값과 두 번째 배열의 첫번째 요소값을 비교한 후, 더 작은 값을 빈 배열에 넣는다. 그리고 다시 두 배열의 값을 비교하고,    더 작은 값을 넣는다.
    e. 둘 중 한 배열에서 변수 i나 j가 끝까지 도달했다면 나머지 배열의 값을 모두 넣는다.

4. 합병함수

a. 직접 구현한 코드인데 진짜 잘 짠 것 같다. 어젯밤에 잠에 들면서 내내 생각했던 것을 구현했더니 금방 되었다. 코드는 colt와 좀 다르지만 로직은 거의 같음.

function merge(arr1, arr2) {
  let array = [];
  let i = 0;
  let j = 0;
  while (arr1.length > i || arr2.length > j) {
    if (arr1[i] <= arr2[j] || arr2.length === j) {
      array.push(arr1[i]);
      i++;
    } else if (arr1[i] >= arr2[j] || arr1.length === i) {
      array.push(arr2[j]);
      j++;
    }
  }
  return array;
}

b. 리팩토링 버전은 추후 수정

5. 분할 및 합병

a. 합병함수를 활용하여 분할 후 다시 합병하는 재귀함수를 만든다.

    function sliceAndMerge(array) {
      if (array.length <= 1) return array;
      const center = Math.floor(array.length / 2);
      let leftArray = sliceAndMerge(array.slice(0, center));
      let rightArray = sliceAndMerge(array.slice(center));
      return merge(leftArray, rightArray);
    }

b. 이건 혼자 풀지 못했음. 보고도 바로 이해하지는 못했고, 디버깅을 돌리면서 이해했다.
c. 시간복잡도 : best, average, worst 모두 O(n log n)이다. 무작위든, 정렬이 어느정도 되어있든 결국 다 분할한 다음 다시 합병한다.
i. 분할할 때 시간복잡도는 log n이며 분할된 배열을 다시 합병할 때 O(n)인데 분할 단계마다 합병을 하니까 곱하기를 해줘야 한다.
공간복잡도 : O(n)