Exercise 3: A Second Refactor to Insertion Sort — Possible Solution
====================================================================

THE NEW IMPLEMENTATION
------------------------------
    class SorterInsertion:
        def sort(self, items):
            items = items[:]
            self.comparisons_made = 0
            for i in range(1, len(items)):
                key = items[i]
                j = i - 1
                while j >= 0:
                    self.comparisons_made += 1
                    if items[j] > key:
                        items[j + 1] = items[j]
                        j -= 1
                    else:
                        break
                items[j + 1] = key
            return items

RESULTS
------------------------------
    test_behavior_only PASS: True
    sorted output: [1, 2, 3, 4]
    comparisons made by insertion sort: 6

    (bubble sort's own count, from the chapter, was also 6 - same)

test_behavior_only passes completely unmodified, exactly as expected -
it never depended on how the sort was implemented.

A GENUINE COINCIDENCE, VERIFIED BY HAND TRACE
------------------------------
Insertion sort's own comparison count on [4, 2, 3, 1] happens to also
be 6, matching bubble sort's own count on the same input, even though
the two algorithms compare completely different pairs of elements in a
completely different order:
  i=1 (key=2): 1 comparison (4>2)
  i=2 (key=3): 2 comparisons (4>3, then 2>3)
  i=3 (key=1): 3 comparisons (4>1, 3>1, 2>1)
  total = 1 + 2 + 3 = 6

This is coincidental to this specific 4-element input, not a general
property of insertion sort - a different input array would very likely
produce a different comparison count than bubble sort's own count on
that same input.

WHY THIS WORKS AS AN ANSWER
------------------------------
This is a useful, honest complication of the chapter's own point rather
than a clean repeat of it: an implementation-detail test asserting
comparisons_made == 6 would, by coincidence, still pass against THIS
particular refactor and THIS particular input - even though the
underlying algorithm is completely different from what the test was
originally written to describe. That's arguably a worse outcome than a
clean failure: a brittle test that happens to still pass gives false
confidence that nothing about the implementation changed, when in fact
everything about it did. The behavior-only test is unaffected either
way, which is exactly why it's the one to trust.