Merge sort and divide-and-conquer recurrence
Split an array into two nearly equal halves, sort each recursively, and merge sorted halves by repeatedly choosing the next ordered key.
Key knowledge
Split an array into two nearly equal halves, sort each recursively, and merge sorted halves by repeatedly choosing the next ordered key. Merge work is Θ(n), so T(n)=T(⌊n/2⌋)+T(⌈n/2⌉)+Θ(n) gives Θ(n log n) time.
Conditions and scope
- Base cases have at most one element; comparisons and array operations are bounded-cost.
- A usual array merge uses Θ(n) auxiliary storage; this is a comparison-sort guarantee.
Sources · 1
References
Sources retain their recorded scope. A source link alone does not establish verification of every statement.
Evidence and review
Lecture 3 transcript pages 11–14: two-pointer merge, recursive split and runtime recurrence; rounded halves stated explicitly.
2026-10-10 · Independent AI editorial review: All241 compact claims, hypotheses, displayed equations/conventions and all596 origin semantic links read; entire241-entry author exact-source inspection matrix and declared limitations reviewed. Prior105 actual inherited Mathematics/Information records read for whole-inventory breadth. Targeted independent primary sections are listed below; this does NOT claim every cited source body or every proof was independently re-read. This is AI reference-content review, not human disciplinary certification, exhaustive textbook reproduction or experimental replication. Receipt: mathematics-information-independent-content-review.1.
Entry details
Permanent link to this entry ↗- Record identity
- info-merge-sort
- Revision
- university-core.1
- Structured reference record
- University core expansion