Overview
Odd-Even Merge Sort is a sorting method that orders values by a named comparison, distribution, merge, or parallel network rule. It is useful when its stability, memory use, parallelism, or data-movement pattern fits the workload.
CoreSource checked
Odd-Even Merge Sort
Odd-Even Merge Sort sorts with a fixed comparison network suited to parallel execution.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Sorting
- Difficulty
- Intermediate
- Family
- Sorting
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 0
- Relationships
- 1
- Code example
- Ready
- Visualization
- Ready
Core Concepts
ordering relationcomparison stepdata movementordering rulecomparisonrearrangement
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n)
Average
O(n log n)
Worst
O(n log n)
Space
O(n)
When to Use
- Use Odd-Even Merge Sort when its stability, memory, parallelism, or movement pattern fits the data.
- Use it when the input shape is known enough to choose beyond a generic library sort.
When Not to Use
- Avoid when a simpler standard library sort already gives the needed stability and performance.
- Avoid when the method's memory or data-movement pattern conflicts with the storage medium.
What It Does
- Reorders items by key
- Compares, partitions, merges, or distributes records
- Returns a sorted sequence
Use Cases
- Preparing data for search
- Ranking records
- External or parallel ordering
Inputs
- Unordered collection
- Comparison or key function
Outputs
- Ordered collection
- Partitioned or partially ordered collection
Pseudocode
- 1.Split, compare, distribute, or merge items according to the method
- 2.Maintain the method's ordering invariant
- 3.Move records into progressively more ordered positions
- 4.Repeat until every item is ordered
- 5.Return the sorted collection
Canonical Example
- Input
- values = [4, 1, 3, 2]
- Output
- [1, 2, 3, 4]
- Explanation
- Odd-Even Merge Sort applies its ordering rule until all values are in sorted order.
Implementation Notes
- Document whether equal keys preserve original order.
- Benchmark on realistic input shapes, not only random arrays.
Common Pitfalls
- Mixing stable and unstable variants can reorder equal keys unexpectedly.
- Ignoring cache or external-memory behavior can dominate theoretical complexity.
Interactive Mechanism Walkthrough
Array Partition & Ordering TraceShow elements moving through compare, swap, merge, or distribution steps.
38[0]
14[1]
52[2]
23[3]
61[4]
19[5]
44[6]
29[7]
Step 1 of 5: Split, compare, distribute, or merge items according to the method
sortingNotes
Odd-Even Merge Sort operates in O(n log n) time and O(n) space within the Sorting family. Often compared with Merge Sort and Quick Sort.
Sources (2)
What each reference supports for this entry.
The Art of Computer Programming, Volume 3
BookSorting and searching reference covering Odd-Even Merge Sort comparison model, probe strategy, network structure, or pass schedule.
Batcher Sorting Networks
PaperOriginal sorting-network reference supporting odd-even merge sort networks and parallel compare-exchange stages.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageConceptual neighborMerge Sort
Odd-Even Merge Sort and Merge Sort address nearby sorting problems but make different implementation tradeoffs.
Related Algorithms
Tags
Sorting