주어진 데이터를 정렬하기 위해 다음의 과정을 거칩니다. 1. 전체 데이터를 둘로 나눕니다. 2. 각 부분이 정렬되어 있다면, 순서에 맞게 두 배열을 합칩니다. 3. 1번과 2번을 둘로 나눈 데이터의 각 부분에 똑같이 적용시킵니다. 이렇게 더 이상 나눌 수 없을 때까지 데이터를 나눕니다. 이것을 Recurrence Equation으로 표현하면 다음과 같다. $ T(n) = 2T(\frac{n}{2}) + cn, (n\ge2) \newline T(1) = 1 $ Divide에 해당하는 1번 과정은 O(1)이라 식에 표현되어 있지 않고, Conquer에 해당하는 2번 과정은 $2T(\frac{n}{2}$) 이며, Combine에 해당하는 3번 과정은 cn이다. 정확히 둘로 나누면 그렇다는 것이고, 일반적으로 n개의 원소를 k개와 l개로 나누어 진행한다고 가정하면, $ T(n) = T(k)+T(l)+cn $ 이렇게 표현할 수 있다. 두 가지 경우 모두 시간 복잡도가 O(nlogn)이다.