✦ScienexySCIENCE KNOWLEDGE LIBRARY
General science · SCI-FORM-COM-2067

Merge Sort Time Complexity Relation

Merge sort divides an array into two approximately equal halves, recursively sorts each half, and combines the sorted halves through a linear-time merge operation. Its best-case, average-case, and worst-case time complexities are all Θ(n log n).

\(T(n) = 2T(n/2) + \Theta(n) = \Theta(n log_{2} n)\)

What this formula means

Merge sort divides an array into two approximately equal halves, recursively sorts each half, and combines the sorted halves through a linear-time merge operation. Its best-case, average-case, and worst-case time complexities are all Θ(n log n).

Scientific principle

Principle

The recursive division creates approximately log₂ n levels of subproblems. At each level, merging processes a total of approximately n elements. Multiplying the number of levels by the work per level gives the overall Θ(n log n) complexity.

Derivation

  • 1. Let n be the number of elements.

  • 2. Merge sort divides the input into two subproblems of approximately n/2 elements.

  • 3. Each subproblem is sorted recursively.

  • 4. Merging the two sorted halves requires Θ(n) time.

  • 5. Therefore, T(n) = 2T(n/2) + Θ(n), with T(1) = Θ(1).

  • 6. The recursion tree has approximately log₂ n levels.

  • 7. Each level performs Θ(n) total merging work.

  • 8. Therefore, total work is Θ(n log₂ n).

Final Result

T(n) = Θ(n log₂ n)

Recurrence Relation

T(n) = 2T(n/2) + Θ(n)

Recursion Depth

Θ(log₂ n)

Work Per Level

Θ(n)

Variables and their meanings

SymbolMeaningUnit

T(n)

Execution time for sorting n elements

Time or abstract operation count

n

Number of elements to be sorted

Elements

T(n/2)

Execution time for sorting one half of the input

Time or abstract operation count

log₂ n

Approximate number of recursive division levels

Levels

SI units and conversions

Execution Time

Depends on the computational environment

Input Size

Number of elements

Asymptotic Complexity

Θ(n log n)

Conditions of use

  • The input is recursively divided into approximately equal halves.

  • The merge operation takes linear time in the total number of elements being merged.

  • The base case handles arrays of size one or zero.

  • The analysis assumes a conventional comparison-based merge sort.

Limitations and assumptions

  • The asymptotic formula does not specify exact execution time.

  • Conventional array-based merge sort generally requires Θ(n) auxiliary memory.

  • Recursive function-call overhead is not represented separately in the asymptotic result.

  • Actual performance depends on memory layout, allocation, cache behavior, and implementation.

  • The standard implementation is stable when equal elements are handled consistently during merging.

Step-by-step worked examples

ProblemSolutionAnswer

Estimate the number of merge-sort recursion levels and the total work per level for an array containing 1,024 elements.

  • Given: n = 1,024.

  • Recursion depth is approximately log₂ n.

  • log₂ 1,024 = 10.

  • Therefore, there are approximately 10 division levels before reaching single-element subproblems.

  • Each level performs Θ(1,024) total merging work.

  • Total asymptotic work is Θ(1,024 × 10).

  • This gives an order of approximately 10,240 units of level-wise work, ignoring constants and base-case details.

The recursion depth is approximately 10 levels, and the total complexity is Θ(1,024 log₂ 1,024) = Θ(10,240).

Compare the asymptotic growth of merge sort for input sizes 1,000 and 2,000 using n log₂ n as the growth measure.

  • For n = 1,000: n log₂ n ≈ 1,000 × 9.966 ≈ 9,966.

  • For n = 2,000: n log₂ n ≈ 2,000 × 10.966 ≈ 21,932.

  • Growth ratio ≈ 21,932/9,966.

  • Growth ratio ≈ 2.20.

Doubling the input size increases the n log₂ n growth measure by approximately 2.20 times.

Real-world applications

  • Large-scale data sorting

  • External sorting of datasets larger than memory

  • Stable sorting implementations

  • Parallel sorting algorithms

  • Sorting linked lists

Formula Meaning

Merge sort divides an array into two approximately equal halves, recursively sorts each half, and combines the sorted halves through a linear-time merge operation. Its best-case, average-case, and worst-case time complexities are all Θ(n log n).

Sources and further reading

No source has been supplied for this item yet. Treat the claim as needing editorial verification.

← Back to Formula Hub · Suggest a correction or source