Merge is an efficient, general-purpose, and comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the order of equal elements is the same in the input and output.
| Time (middle/the worst) | Memory (middle/the worst) |
|---|---|
| O(n log n)/O(n log n) | O(n)/O(n) |