merge sort

항상 절반씩 나눠서 실행하기 때문에 최악의 경우도 똑같이 O(Nlog(N))이다. 단점이라고 한다면 정렬된 배열을 담을 임시 배열이 하나 더 필요하다. 그래서 메모리 공간을 조금 더 사용한다는 단점이 있다.
병합 정렬도 분할 정복을 이용하기 때문에 퀵 정렬과 똑같이 O(Nlog(N))이다. 퀵 정렬과 다르게 피봇값이 없다.