정렬 알고리즘을 이야기하다보면, 항상 비교되는 두가지가 퀵 소트와 머지 소트이다. 일반적인 상황에서 두 정렬의 복잡도는 O(nlogn)으로 표기한다. 두 정렬을 구태여 비교하는 이유는 분할 정복(divide and conquer) 패러다임을 이용하기 때문이다. 임의의 배열이 있을 때 반으로 쪼개어 가면서 각 원소를 순서대로 배치하는데, 퀵 소트는 분할 이전 그리고 머지 소트는 분할 이후에 이를 순서대로 배치한다. 좀 더 쉽게 그림으로 보자. 왼쪽 머지 소트는 배열을 1/2씩 나눠가면서 정렬이 되었을 때까지 계속해서 나누어간다. 만약 원소가 1개가 된다면 부분 배열은 정렬된 상태이므로 그 다음부터는 합쳐가면서 다시금 배열을 조립한다. 이 합치는 과정은 각 부분 배열의 길이와 같으므로 O(N)이 걸리게 된다..
