Trace Insertion Sort
What does insertion sort do with each new item?
It inserts each new item into the correct position in the sorted left part.
What does a correct algorithm do?
It gives the right answer for valid inputs.
What does time complexity describe?
How running time grows as input size grows.
What design strategy does merge sort use?
Divide and conquer.
For a large unsorted array, which is usually more suitable?
Merge sort.
In insertion sort, which part remains sorted after each step?
The processed left part.
What is an invariant?
Something that remains true as the algorithm runs.
What is insertion sort’s best-case time complexity?
O(n)
What are merge sort’s three main steps?
Divide, sort recursively, and merge.
When can insertion sort still be useful?
It is simple and works well for small or nearly sorted inputs.
In [12, 38, 45], where should 29 be inserted?
Between 12 and 38.
What is the key invariant in insertion sort?
After each step, the processed left part remains sorted.
What is the base case in merge sort?
O(n^2)
Why is a one-element array already sorted?
There is nothing out of order.
Why does merge sort scale better for large unsorted inputs?
Its O(n \log n) grows more slowly than O(n^2).
After inserting 29 into [12, 38, 45, 29, 7], what is the array?
[12, 29, 38, 45, 7]
How does the invariant support correctness?
It shows each step preserves sorted order.
Why does O(n^2) become costly for large inputs?
The number of comparisons and shifts grows very quickly.
Why does merge sort have about (\log n) levels?
Because the array is repeatedly divided in half.
What trade-off may favour insertion sort over merge sort?
Insertion sort uses less extra space.
Why can insertion sort work well on nearly sorted input?
Few elements need to move.
Why is the whole array sorted when insertion sort ends?
All elements have been processed into the sorted part.
Which grows more slowly for large (n): O(n^2) or O(n \log n)?
O(n \log n)
Why is merge sort O(n \log n)?
There are about (\log n) levels, and each level processes (n) elements.
What is the main lesson in algorithm choice?
Correctness matters, but efficiency and context also matter.