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

합병정렬(병합정렬, Merge Sort) - 전체 데이터를 하나의 단위로 분할한 후 분할한 것들을 다시 병합하는 정렬 방식 - 분할 정복 알고리즘에 속함 (분할 정복 : 어떤 문제를 그대로 해결할 수 없을 때 작은 문제로 분할해서 푸는 방법) 시간 복잡도 O(NlogN) - 최선이든 최악이든 같음 장점 - 어떠한 경우에도 좋은 성능을 보장한다. - 중복된 데이터의 순서가 바뀌지 않는 stable한 정렬이다. 단점 - 30 개 이하의 숫자를 정렬할 때는 삽입 정렬과 별 차이가 없음 - 정렬하는데 추가 메모리가 필요함 (in-place 알고리즘이 아님) 구현 function mergeSort(array) { if (array.length < 2) { return array; } let pivot = Math..

2021.05.05