Overview
Merge Sort divides the input into smaller halves, sorts each half, and merges two sorted sequences by repeatedly taking the smaller front item.
FoundationSource checked
Merge Sort
Sorts a list by recursively sorting halves and merging the sorted results.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Sorting
- Difficulty
- Intermediate
- Family
- Divide and Conquer
- Tier
- Foundation
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 0
- Relationships
- 11
- Code example
- Ready
- Visualization
- Ready
- Aliases
- Mergesort
Core Concepts
divide and conquermerge stepstable orderingauxiliary buffer
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n log n)
Average
O(n log n)
Worst
O(n log n)
Space
O(n)
When to Use
- Use it when predictable O(n log n) time is important.
- Use it when stable sorting is required.
- Use it for linked lists or external sorting where sequential merging is natural.
When Not to Use
- Avoid it when extra memory is too expensive and an in-place sort is required.
- Avoid it for tiny arrays unless it is part of a hybrid sort.
What It Does
- Divides a list into smaller lists
- Merges sorted lists into a larger sorted list
Use Cases
- Stable general-purpose sorting
- Sorting linked lists
- External sorting
Inputs
- Array, list, or linked list of comparable values
Outputs
- Sorted collection
Pseudocode
- 1.Split the list into two halves
- 2.Recursively sort each half
- 3.Compare the front items of both halves
- 4.Move the smaller front item into the result
- 5.Append any remaining items
Canonical Example
- Input
- array = [4, 1, 3, 2]
- Output
- [1, 2, 3, 4]
- Explanation
- It sorts [4, 1] and [3, 2] separately, then merges [1, 4] with [2, 3].
Implementation Notes
- Use one reusable auxiliary buffer when possible.
- Define the merge contract carefully: both input ranges must already be sorted.
- Switch to insertion sort for very small subarrays in production implementations.
Common Pitfalls
- Allocating many short-lived temporary arrays unnecessarily.
- Breaking stability by taking from the right side first when keys compare equal.
- Forgetting to copy any remaining tail from either half during merge.
Interactive Mechanism Walkthrough
Array Partition & Ordering TraceShow the list splitting into halves and merging back in sorted order.
38[0]
14[1]
52[2]
23[3]
61[4]
19[5]
44[6]
29[7]
Step 1 of 5: Split the list into two halves
divide-mergeNotes
Merge sort's predictable runtime makes it useful when worst-case quicksort behavior is unacceptable.
Sources (1)
What each reference supports for this entry.
Introduction to Algorithms (CLRS)
BookTextbook support for Merge Sort invariants, recurrences, relaxation rules, or asymptotic analysis.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Alternative toQuick Sort
Sorting · Foundation
Merge Sort guarantees n log n time and stable merging, while Quick Sort partitions in place.
Compare with thisUsed byNatural Merge Sort
Sorting · Core
Natural Merge Sort uses Merge Sort as a subroutine, representation, or supporting idea while detecting existing sorted runs and merging them.
Compare with thisUsed byTim Sort
Sorting · Core
TimSort merges detected runs using merge-sort-style stable merging.
Compare with thisUsed byExternal Sort
Sorting · Extended
External sorting commonly creates sorted runs and merges them with merge-sort-style passes.
Compare with thisRelationships
View full relationship pagePrerequisite ofParallel Merge Sort
Parallel merge sort extends merge sort by distributing recursive work.
Alternative toQuick Sort
Merge Sort guarantees n log n time and stable merging, while Quick Sort partitions in place.
Related Algorithms
Tags
Comparison SortDivide and ConquerStable SortRecursion