Skip to content
doubtly

1 answer

Sorted list: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. Merge sort satisfies \(T(n) = 2T(n/2) + cn\), which gives \(O(n\log n)\).

Divide (mid = ⌊(low + high)/2⌋, positions 1 to 10):

[10, 5, 7, 6, 1, 4, 8, 3, 2, 9]
[10, 5, 7, 6, 1]          [4, 8, 3, 2, 9]
[10, 5, 7]  [6, 1]        [4, 8, 3]  [2, 9]
[10, 5] [7] [6] [1]       [4, 8] [3] [2] [9]
[10] [5]                  [4] [8]

Merge (bottom up):

[10] + [5]           -> [5, 10]
[5, 10] + [7]        -> [5, 7, 10]
[6] + [1]            -> [1, 6]
[5, 7, 10] + [1, 6]  -> [1, 5, 6, 7, 10]

[4] + [8]            -> [4, 8]
[4, 8] + [3]         -> [3, 4, 8]
[2] + [9]            -> [2, 9]
[3, 4, 8] + [2, 9]   -> [2, 3, 4, 8, 9]

[1, 5, 6, 7, 10] + [2, 3, 4, 8, 9]
                     -> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Algorithm:

MergeSort(low, high):
  if low < high:
    mid = (low + high) / 2
    MergeSort(low, mid)
    MergeSort(mid + 1, high)
    Merge(low, mid, high)   // merge two sorted halves

Computing time: merging two sorted lists with a total of \(n\) elements takes at most \(n\) comparisons, i.e. \(cn\). So

\[T(n) = 2T(n/2) + cn,\quad T(1) = a\]

Substituting repeatedly, with \(n = 2^{k}\):

\[T(n) = 4T(n/4) + 2cn\]

\[= 2^{k}T(1) + k\,cn\]

\[= an + cn\log_2 n\]

Hence \(T(n) = O(n\log n)\) in the best, average and worst cases. It needs \(O(n)\) extra space for merging.

Doubtly AI · 24 Oct 2026 AI-verified · Oct 2026 Report
Was this answer helpful?

Your answer

Log in or create a free account to answer this question.