[JS]합병 정렬(merge sort)

합병 정렬(merge sort)알고리즘의 개념

1. 일반적인 방법으로 구현했을 때 이 정렬은 안정 정렬 에 속하며, 분할 정복 알고리즘의 하나 이다.
2. 분할 정복(divide and conquer) 방법
3. 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다.
4. 분할 정복 방법은 대개 순환 호출을 이용하여 구현한다

합병 정렬(merge sort) 알고리즘의 구체적인 개념

1. 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다.
2. 합병 정렬은 다음의 단계들로 이루어진다.
   a. 분할(Divide): 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다.
   b. 정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출 을 이용하여 다시 분할 정복 방법을 적용한다.
   c. 결합(Combine): 정렬된 부분 배열들을 하나의 배열에 합병한다.
3. 합병 정렬의 과정
   a. 추가적인 리스트가 필요하다.
   b. 각 부분 배열을 정렬할 때도 합병 정렬을 순환적으로 호출하여 적용한다.
   c. 합병 정렬에서 실제로 정렬이 이루어지는 시점은 2개의 리스트를 합병(merge)하는 단계 이다.

합병 정렬(merge sort)알고리즘 예제

2개의 정렬된 리스트를 합병(merge)하는 과정
a. 2개의 리스트의 값들을 처음부터 하나씩 비교하여 두 개의 리스트의 값 중에서 더 작은 값을 새로운 리스트(sorted)로 옮긴다.
b. 둘 중에서 하나가 끝날 때까지 이 과정을 되풀이한다.
c. 만약 둘 중에서 하나의 리스트가 먼저 끝나게 되면 나머지 리스트의 값들을 전부 새로운 리스트(sorted)로 복사한다.
d. 새로운 리스트(sorted)를 원래의 리스트(list)로 옮긴다.

참고문헌

https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

이후 계속..