Phân tích, trao đổi, thảo luận để tính độ phức tạp thời gian của thuật toán sắp xếp trộn.

Gọi T(n) là thời gian chạy của thuật toán sắp xếp trộn.

Với n = 1, dòng lệnh 2 trả lại ngay dãy gốc A, do đó T(1) = 1.

Trường hợp tổng quát

- Tại bước chia (dòng 5), cần O(1) thời gian để thực hiện.

- Các dòng 6, 7 sẽ mất 2T(n/2) thời gian.

- Dòng lệnh 8 thực hiện trộn hai dãy với thời gian O(n).

Tổng kết lại chúng ta các công thức sau tính thời gian T(n).

T(1)=1

T(n) = 2T(n/2) + O(n), n > 1     (1)

Không mất tổng quát, giả sử tồn tại hằng số C > 0 sao cho:

T(n) = 2T (n/2)+ Cn, n > 1        (2)

Các công thức (1), (2) được gọi là công thức truy hồi để tính độ phức tạp thời gian T(n)
của thuật toán trộn.

Người ta tính được: T(n) = O(nlogn).