[알고리즘] 정렬(5) - 병합 정렬(Merge Sort)

원리 1. 정렬할 배열을 사이즈가 1이 될때까지 반으로 나눈다. (분할) 2. 나눌 수 없을때까지 나눈뒤 정렬을 한다. (정복) 3. 정렬 한 결과를 병합한다. (병합) [ 16, 11, 6, 19, 12, 2, 2, 10 ] 정렬하기에 앞서 분할 정복(Divide and conquer)을 이해하고 있어야합니다. 모르더라도 이번 기회에 직접 이해해 보도록 하겠습니다. 분할은 배열을 절반씩 나누어서 사이즈가 1이 될때까지 나눈 것입니다. 그리고 정렬을 하고 병합을 하는 식으로 구성되어있습니다. 방식은 쉽게 이해하실 수 있습니다. 그렇다면 왜 굳이 분할을 해서 다시 합치면서 정렬을 해야할까요? 이는 아래 시간복잡도를 알아보면서 이해해보도록 하겠습니다. 구현 template vector MergeSort(co..

2020.04.09