JavaScript로 Merge Sort(병합정렬) 구현하기

JavaScript, Recursion

돌파구

병합정렬은 크게 두 가지 함수로 이루어져 있다.

1. function merge(left, right) : 이미 소팅된 배열 left, right 받아서 하나로 합치는 순수한 함수
2. function mergeSort(arr) : 배열을 반으로 쪼개서 merge 함수에게 left, right 인자를 넘겨주는 함수

이 때, merge함수는 순수한 함수이고, mergeSort는 재귀로 함수를 콜한다는 것을 인지해야 한다.

merge function

merge 함수는 이미 정렬 된 left(배열), right(배열)를 인자로 받아서 하나로 합치는 기능

mergeSort function

mergeSort 는 반으로 쪼개서 merge 에게 인자를 넘겨주는 기능

구현