1) 병합 정렬이란? 정렬하고 싶은 수열을 두 개의 수열로 분할해 간다. 더 이상 분할되지 않는 상태(즉, 각 그룹이 한 개의 숫자가 된 경우) 그룹들을 병합해 나간다. 병합할 때에는 정렬이 끝난 두 개의 수열을 병합해서 정렬이 끝난 하나의 수열로 만들고, 이것을 전체가 하나의 그룹이 될 때까지 반복한다. 2) 병합 정렬의 시간복잡도 병합 정렬에서 숫자를 분할해 갈 때는 계산 시간이 걸리지 않는다. 사실상 처음부터 분할된 상태라고 생각해도 무방하다. 두 개의 정렬이 끝난 수열을 병합하는 부분은, 선두의 수를 비교해서 작은 쪽을 위로 올리는 것을 반복하는 것이 전부이므로 두 수열의 길이에 따라 달라진다. 따라서 하나의 층에서 병합 계산 시간은 그 층에 있는 숫자의 수가 된다. 어떤 층을 봐도 숫자는 n개 ..