감공사

✨ 합병 정렬 또는 병합 정렬(Merge Sort)는 O(n log n) 비교 기반 정렬 알고리즘이다.
일반적인 방법으로 구현했을 때 이 정렬은 안정 정렬에 속하여, 분할 정복 알고리즘의 하나이다.

Merge Sort는 Merge Sort(분할), Merge(병합) 2가지 function으로 나눠서 작성할 수 있다.
Merge를 구현하는 function을 먼저 작성해보겠다.

[ -30, 22] [ 0, 97 ]

위 left, right 배열에 들어있는 숫자를 오름차순으로 정렬해보자

🎈 Merge function을 실행하면 위와 같은 과정으로 정렬이 진행된다.

각 배열의 가장 첫 번째 값들을 비교하고, 작은 값을 먼저 넣어준다.
이렇게 Merge function은 간단하다. 양쪽 배열을 비교하고 작은 값을 먼저 넣어주면 된다.

아래 Pseudo Code와 이미지를 참고하여 코드를 작성해보자.

🧨 left, right 2개의 argument를 받고
둘 중 하나의 배열값이 모두 shift()될 때까지 while loop을 반복한다.
가장 첫 번째 index를 비교하고 작은 값을 results 배열에 넣어준다.
둘 중 하나의 배열은 1개의 값이 존재할 것이므로, return 부분에는 result, left, right를 모두 spread해준다.

이렇게 Merge Function을 먼저 작성해줄 수 있다.

다음은 Merge의 전 단계인 MergeSort Function을 작성해보자(각 배열 분할 기능)

[ 97, 0, 22, -30 ]

위의 배열을 length가 1을 가질 때까지 분할해보자.
이 기능은 끝이 정해져 있는 반복이므로, 재귀를 통해 해결할 수 있다.

🎈 Merge Sort function을 실행하면 위와 같은 과정으로 정렬이 진행된다.
처음에는 전체 배열의 반으로, 왼쪽에서 또 반으로, 오른쪽에서 또 반으로 반복하여 나눠진다.

아래 이미지를 보며 코드를 어떻게 작성할지 생각해보자.
참고로, Merge Sort는 Merge와 함께 사용할 수 있다.

🧨 먼저, Base Case로 arr.length가 1이 되면 그 값을 반환하도록 한다. 우리의 목표는 1개가 남기까지 분할하는 것이기 때문이다.
배열을 반으로 나누는 기능은, Array의 slice helper method를 이용하면 간편하다.
배열의 중앙 기준을 잡기 위해 center를 구해주고,
그 기준으로 slice(0, center), slice(center)를 진행해주면 left와 right를 구할 수 있다.
( Math.floor(), slice() 사용법은 JavaScript - helper Method 카테고리에서 확인 가능)

그리고 마지막으로, 이 나눠진 element를 merge function을 이용해서 병합해주면 된다.

Merge Sort와 Merge Function이 진행되는 전체 이미지