[알고리즘] 정렬 - 합병정렬(병합정렬, Merge Sort) (자바스크립트/javascript)

합병정렬(병합정렬, Merge Sort)

- 전체 데이터를 하나의 단위로 분할한 후 분할한 것들을 다시 병합하는 정렬 방식

- 분할 정복 알고리즘에 속함

  (분할 정복 : 어떤 문제를 그대로 해결할 수 없을 때 작은 문제로 분할해서 푸는 방법)

 

시간 복잡도

O(NlogN) - 최선이든 최악이든 같음

 

장점

 - 어떠한 경우에도 좋은 성능을 보장한다.

 - 중복된 데이터의 순서가 바뀌지 않는 stable한 정렬이다.

단점

 - 30 개 이하의 숫자를 정렬할 때는 삽입 정렬과 별 차이가 없음

 - 정렬하는데 추가 메모리가 필요함 (in-place 알고리즘이 아님)

 

---

구현

function mergeSort(array) {
  if (array.length < 2) {
    return array;
  }
  let pivot = Math.floor(array.length / 2);
  let left = array.slice(0, pivot);
  let right = array.slice(pivot, array.length);
  return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right) {
  let 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());
  }
  return result;
}
const array = [5, 2, 4, 7, 6, 1, 3, 8];
console.log(mergeSort(array));

merge 함수 부분에서 left 배열의 첫번째 원소랑 right 배열의 첫번째 원소를 비교하는 부분에서, 

왼쪽 첫번째 원소가 오른쪽 첫번째 원소보다 작거나 같다면 result 배열에 왼쪽 것을 빼다가 넣어주기 때문에 

같다가 이쪽에 들어있으므로 왼쪽게 먼저 빠지니까 중복된 데이터의 순서가 바뀌지 않는다. (여기서 같다를 빼버리면 두 값이 같으면 오른쪽 것이 먼저 result 배열에 들어가게 되니까 중복된 데이터의 순서는 바뀔 것이다)

 

참조한 사이트

www.zerocho.com/category/Algorithm/post/57ee1fc107c0b40015045cb4

im-developer.tistory.com/134

[JS/Sorting] 병합 정렬(Merge Sort)과 분할 정복 전략(Divide and Conquer) 개념에 대하여