Aim

To implement Insertion Sort in PHP, tracing each insertion to show how the sorted prefix absorbs one new element per pass — the way a card player sorts a hand.

Theory

Insertion Sort maintains a sorted prefix [0 .. i-1]. Each pass takes the next element (the key), shifts every larger prefix element one slot right, and drops the key into the gap.

Analytical profile:

• Worst case (reverse-sorted): O(n²) — every key travels to the front.
• Best case (already sorted): O(n) — the while-condition fails immediately each pass; the algorithm is adaptive, its runtime is O(n + d) where d is the number of inversions.
• Space: O(1), in place. Stability: stable — shifting uses strict >, so equal elements keep their relative order.
• It is an online algorithm: it can sort a stream as elements arrive, unlike Selection Sort which must see the whole array.
• Real-world relevance: hybrid sorts (Timsort, introsort — used inside Python, Java, and C++ standard libraries) switch to insertion sort for small partitions (~16 elements) because its constant factors are tiny.

Shifting vs swapping: Bubble Sort moves an element with repeated swaps (3 writes each); Insertion Sort shifts with single writes and places the key once — fewer memory writes for the same movement.

Requirements

• XAMPP/WAMP with PHP 8.x, or PHP CLI
• Code editor; browser or terminal

Procedure

1. Start Apache from the XAMPP Control Panel.
2. Save the snippet as p06c_insertion_sort.php in C:\xampp\htdocs\wbplab.
3. Run http://localhost/wbplab/p06c_insertion_sort.php or php p06c_insertion_sort.php.
4. Run it on [1, 2, 3, 4, 5] and observe each pass makes zero shifts (best case), then on [5, 4, 3, 2, 1] for the worst case.

Explanation of the Code

• function insertionSort(array $data): array — typed signature, works on a copy of the caller's array.
• The outer loop starts at $i = 1: a single element (index 0) is trivially sorted.
• $key = $data[$i]; saves the element being inserted, freeing its slot for shifting; $j = $i - 1 points at the last sorted element.
• The core is while ($j >= 0 && $data[$j] > $key) — note the order of the conditions: the bounds check $j >= 0 must come first because && short-circuits, preventing a negative-index read. Each iteration copies $data[$j] one slot right ($data[$j + 1] = $data[$j];) and decrements $j.
• $data[$j + 1] = $key; finally lands the key just after the first element not greater than it, and each pass prints the state with implode.

Expected Output

Original: 7, 5, 4, 2
Step 1: 5, 7, 4, 2
Step 2: 4, 5, 7, 2
Step 3: 2, 4, 5, 7
Insertion Sort: 2, 4, 5, 7

Each step shows one more element absorbed into the sorted prefix.

🎯 Viva Questions

1. Why does the outer loop begin at index 1? A one-element prefix is already sorted; the first key is element 1.
2. Best-case complexity and the input that achieves it? O(n), on an already-sorted array — the inner while never fires.
3. Why must $j >= 0 be tested before $data[$j] > $key? Short-circuit evaluation prevents reading index −1.
4. Shift vs swap — why is shifting cheaper? A shift is one write; a swap is three — the key is written only once at the end.
5. What makes Insertion Sort "online"? It can integrate new elements as they arrive without reprocessing the whole array.
6. Where does insertion sort appear in production libraries? As the small-partition base case inside Timsort and introsort.

CO Mapping

CO1, CO2