병합 정렬

배열을 반으로 계속 나눠 원소 하나짜리 조각까지 만든 뒤, 정렬된 두 조각을 하나로 합치기를 반복하는 정렬이다. 입력이 어떻든 항상 O(n log n)이지만, 두 조각을 합칠 때 결과를 담을 임시 배열이 입력 크기만큼 필요해서 공간 복잡도가 O(n)이다.