Sorting methods compared
↑At a glance
Section titled “At a glance”Insertion sort grows a sorted prefix by inserting each new value into its place. Merge sort recursively divides the data and combines sorted halves. Both produce an ordered result, but they perform different work depending on the input.
| Insertion sort | Merge sort | |
|---|---|---|
| Best case | O(n) |
O(n log n) |
| Worst case | O(n²) |
O(n log n) |
| Typical extra array memory | O(1) |
O(n) |
| Stable in conventional implementations | Yes | Yes, when equal values come from the left first |
Compare the same input
Section titled “Compare the same input”COMPARE SORTING METHODS
Same values, different work
Count comparisons needed to sort the same list. These are algorithm operations, not elapsed time.
The bars count element comparisons in the implementations used here. They do not represent runtime in milliseconds. Try a sorted array and then a reversed array. A nearly sorted array helps insertion sort, while merge sort’s asymptotic behavior is more consistent.
Why does the answer depend on the input?
Section titled “Why does the answer depend on the input?”Insertion sort scans backward only while earlier elements are larger than its current key. With sorted data, it makes one comparison per new element and performs no shifts. With reversed data, the key moves all the way to the left on every pass. The total work then grows quadratically.
Merge sort uses a divide-and-conquer strategy. It splits until ranges are trivial, then compares the front elements of sorted ranges while merging them. Its recursion depth grows logarithmically, and each level processes the elements in linear time.
Check your understanding
Section titled “Check your understanding”Which approach has guaranteed O(n log n) time for a conventional array implementation?
Show the explanation
Merge sort splits into logarithmically many levels and processes n elements per level.