(알고리즘) 합병정렬

합병정렬(merge sort)는 분할정복기법을 사용하는데, n개의 원소를 1개 단위가 될때까지 나누고 병합하면서 정렬하는 방식이다. 아래의 그림을 보면 이해가 빠를것 같다. 시간복잡도는 O(n log n)이고 단점이라면 분할과 병합시의 다른 정렬보다 별도의 공간이 더 필요하다는것이 단점이라고 한다.