Merge Sort 란? 기본적으로 병합정렬은 문제를 분할하고, 분할한 문제를 정복하여 합치는 과정이다. 병합 정렬은 기본적으로 분할 정복(Divide and Conquer) 알고리즘을 기반으로 정렬되는 방식이다. 병합 정렬에 대해 간단하게 말하면 정렬해야 할 리스트가 주어지면 해당 리스트를 분할을 반복하여 최대한 작게 쪼개진 시점에 부분 리스트에서 인접한 원소들끼리 비교하여 정렬하는 방식이다. 병합 정렬은 데이터를 비교하면서 찾기 때문에 비교 정렬이며, 정렬의 대상이 되는 데이터 외에 추가적인 공간을 필요로 하기 때문에 제자리 정렬(in-place sort)가 아니다. 정확히는 제자리 정렬로 구현할 수는 있지만 그 대신 성능을 일부 포기해야 하며 매우 신중하게 구현되어야 한다. 병합 정렬의 구조상 최대..
