병합정렬 자바스크립트

병합 정렬(Merge Sort) 이란

분할 정복 병합 정렬을 학습하기 전에 분할정복에 대해 먼저 알아보자. 분할 정복(Devide and Conquer)이란, 문제를 나눠서 각각을 풀고 다시 합병해서 답을 도출하는 알고리즘이다. 총 Devide, Conquer, Combine의 스텝으로 이루어지며 Devide는 현재 문제가 분할이 가능할 때, 2개 이상의 문제로 나누고 Conquer는 Devide를 통해 나눈 문제가 여전히 분할이 가능하면, 분할된 문제에 재차 Devide를 수행함을 의미한다. Combine은 devide and conquer를 수행하고 더이상 나눠지지 않는 문제를 합병해 답을 도출하는 과정을 말한다. 분할 정복을 채택한 알고리즘에는 대표적으로 병합 정렬, 퀵 정렬 등이 있으며 이미 퀵 정렬은 다루었으니 병합 정렬을 살펴보자..