[Algorithm]합병정렬(merge sort) 알고리즘 C++
대표적인 nlogn 정렬 알고리즘중 마지막인 합병(병합)정렬 이다. 합병정렬은 항상 nlogn 의 성능을 내는 알고리즘으로 힙정렬과 같고 최악상황의 퀵(n^2) 보다 안정적이다. 하지만 평균적으로 퀵정렬보다 느린 성능을 보이며 알고리즘 구현에있어 힙정렬보다 메모리를 더 많이먹는다. 합병정렬 -합병정렬을 쉽게 알수있는 짤(위키백과)- 합병정렬은 분할정복알고리즘이다. 분할정복은 하나의 문제를 잘개 쪼개어(분할하여) 문제를 해결하는 방법임. 합병정렬이 대표적인 분할정복을 사용하는 알고리즘인데. 정렬할 배열을 하나의 원소로 쪼개어 비교하며 정렬하는 방법이다. 이 정렬은 두가지 순서만 알면 되는데. 1.분할 (가장 작은 단위까지 분할)2.정렬 (가장 작은 단위부터 정렬) 과정을 정렬이 완료될때까지 반복이다. 순서..