codaBack to Academy
sorting
Merge Sort
Merge Sort is a stable, divide-and-conquer algorithm that divides the array into halves, recursively sorts each half, and then merges the sorted halves back together. It guarantees O(n log n) performance in all cases.
Use Cases
- •When stable sorting is required
- •Sorting linked lists efficiently
- •External sorting (large files that don't fit in memory)
Complexity Analysis
| Metric | Best | Average | Worst |
|---|---|---|---|
| Time | O(n log n) | O(n log n) | O(n log n) |
| Space | O(n) | ||
Visualization
64
34
25
12
22
11
90
Implementation
Output
Click "Run Code" to see output...