Sorting: Insertion Sort, Merge Sort, and Choosing Between Them
A simple O(n²) sort you can trace by hand, a divide-and-conquer O(n log n) sort, and how to justify choosing one over the other under real, stated constraints.
What you'll learn
- Implement insertion sort and explain why it's O(n^2) worst case but O(n) on nearly-sorted data
- Implement merge sort and explain how its divide-and-conquer structure gives O(n log n)
- Compare two valid sorting algorithms and justify the better choice under stated constraints, not just 'the one with the better Big O'
Prerequisites
Explanation
Insertion sort builds a sorted portion of the array one element at a time: for each new element, shift it leftward past every already-sorted element larger than it, until it lands in its correct position. It's genuinely simple to trace by hand, requires no extra memory beyond the input array (in-place), and — the detail that matters most for choosing when to actually use it — is O(n), not O(n²), when the input is already nearly sorted: each element only needs to shift past the few elements actually out of place, which can be very few. Its worst case (reverse-sorted input) is O(n²), since every new element might need to shift past everything already placed.
Merge sort applies divide-and-conquer directly: divide the array into two halves, recursively sort each half, then merge the two sorted halves into one sorted whole by repeatedly comparing their fronts and taking the smaller. This gives a guaranteed O(n log n) in every case — best, average, and worst — because the divide step always halves regardless of the data's existing order, unlike insertion sort's data-dependent behavior. The cost is memory: a standard merge sort implementation is not in-place, needing O(n) additional space for the merge step's temporary arrays.
Choosing between them is a genuine tradeoff, not a simple "smaller Big O wins" decision — this is the point this lesson's independent exercise asks you to argue explicitly, not just assert: for a small array (where constant factors dominate and n² vs. n log n barely differs numerically), insertion sort's simplicity and lack of extra memory allocation can make it the genuinely better real-world choice, and production sort implementations commonly switch to an insertion-sort-like strategy for small sub-arrays for exactly this reason. For data that's already mostly sorted (a common real-world case — appending a few new records to an already-sorted log), insertion sort's near-linear behavior can beat merge sort's guaranteed-but-fixed O(n log n). For a large, unpredictably-ordered array where a worst-case O(n²) would be unacceptable, merge sort's guarantee is the right call despite the extra memory. "Which one is better" has no single correct answer independent of the actual constraints — array size, existing order, and memory budget all genuinely change which choice is justified.
Example
Both algorithms implemented in full, so their structural difference (shift-in-place vs. divide-merge) is directly visible.
function insertionSort(arr) {
const result = [...arr];
for (let i = 1; i < result.length; i++) {
const current = result[i];
let j = i - 1;
while (j >= 0 && result[j] > current) {
result[j + 1] = result[j]; // shift larger elements right
j--;
}
result[j + 1] = current;
}
return result;
}
function mergeSort(arr) {
if (arr.length <= 1) return arr; // base case
const mid = Math.floor(arr.length / 2);
const left = mergeSort(arr.slice(0, mid)); // conquer
const right = mergeSort(arr.slice(mid)); // conquer
return merge(left, right); // combine
}
function merge(left, right) {
const result = [];
let i = 0, j = 0;
while (i < left.length && j < right.length) {
result.push(left[i] <= right[j] ? left[i++] : right[j++]);
}
return result.concat(left.slice(i), right.slice(j));
}
console.log(insertionSort([5, 2, 8, 1, 9]));
console.log(mergeSort([5, 2, 8, 1, 9]));Try it yourself
Try both sorts on an already-sorted array [1,2,3,4,5] -- insertion sort's while loop should barely execute at all.
Code editor. Press Escape then Tab to leave the editor if keyboard focus becomes trapped. Press Control+Shift+M inside the editor to toggle Tab-key focus trapping.
Guided exercise
Guided exercise
Write insertionSort(arr) (return a NEW sorted array, do not mutate the input) and countShifts(arr) that returns how many shift operations insertionSort would perform on arr (a direct measure of how far from sorted the input already is).
Checks: sorts an unordered array correctly · does not mutate the original input array · already-sorted input requires zero shifts · reverse-sorted input requires substantially more shifts than nearly-sorted input
Code editor. Press Escape then Tab to leave the editor if keyboard focus becomes trapped. Press Control+Shift+M inside the editor to toggle Tab-key focus trapping.
Stuck? Get a hint.
Independent exercise
Independent exercise
Write mergeSort(arr) and a helper merge(left, right), fully implementing merge sort (return a new array; do not mutate the input). Then write recommendSort(arraySize, isNearlySorted) that returns 'insertion' or 'merge', justifying the choice per this lesson's tradeoffs: recommend 'insertion' when arraySize <= 20 (constant factors dominate) OR isNearlySorted is true (insertion sort's near-linear behavior applies); otherwise recommend 'merge' (guaranteed O(n log n) matters more once neither condition holds).
Checks: mergeSort sorts correctly · mergeSort does not mutate its input · mergeSort handles an empty array · recommends insertion sort for a small array · recommends insertion sort for a large but nearly-sorted array · recommends merge sort for a large, unpredictably-ordered array
Code editor. Press Escape then Tab to leave the editor if keyboard focus becomes trapped. Press Control+Shift+M inside the editor to toggle Tab-key focus trapping.
Stuck? Get a hint.
Common mistakes
- Assuming O(n log n) is 'always better' than O(n^2) without considering the actual constraints -- for small arrays or nearly-sorted data, insertion sort can genuinely be the better real-world choice despite its worse worst-case complexity class.
- Implementing merge sort's base case to return the SAME array reference for length <= 1, instead of a copy -- this can cause subtle aliasing bugs where the 'sorted' result shares memory with part of the original input.
- Forgetting that a standard merge sort needs O(n) extra memory for the merge step -- in a genuinely memory-constrained environment, insertion sort's in-place property can matter more than its worse time complexity.
Knowledge check
Takeaway
Insertion sort is simple, in-place, and O(n) on nearly-sorted data but O(n^2) worst case; merge sort guarantees O(n log n) in every case at the cost of O(n) extra memory — choosing between them requires weighing actual array size, existing order, and memory constraints, not just comparing Big O classes in isolation.
Summary
Insertion sort shifts each new element into its correct position among already-sorted elements — O(n^2) worst case, O(n) on nearly-sorted input, in-place. Merge sort divides, recursively sorts, and merges — guaranteed O(n log n), but needs O(n) extra memory. The better choice depends on the actual constraints of the situation, not a single Big-O comparison.
References
Your notes
Notes save automatically.
Finished this lesson?
Mark it complete to track your progress and schedule a future review.
AI tutor
The optional AI tutor isn't enabled in this deployment. All lessons, exercises, quizzes, and search work fully without it.