prompt: You will be provided with a partial code base and an issue statement explaining a problem to resolve.
  <issue>
  improvement to insertion_sort algorithm
  ### Feature description
  
  I was about to make a PR to improve the implementation of [insertion_sort algorithm](https://github.com/TheAlgorithms/Python/blob/master/sorts/insertion_sort.py) but since there might be multiple ways of doing so, I thought I should first ask your opinions.
  
  These are the things that need improvements:
  
  1. We unnecessarily create a whole new copy of the list: `enumerate(collection[1:])`.
  
     We can either use "indexes" to avoid this which is not very pythonic, or we can use the iterator of the list using `iter()` and throw away the first item using `next()`. In second case we have to either check for empty list first or wrap it in a try-except block. I'll go with indexes if you ask. What do you think?
  
  2. I think a function should either mutate the list in-place and returns `None`, or it should create new sorted list without modifying the original list. Mutating the list and returning the mutated list is not what most developers expect to see. What do you think?
  
  3. We can safely remove `if insert_index != temp_index:` condition and unindent its body. Assigning an item to an index of a list is not costly. So it's one less line in general.
  improvement to insertion_sort algorithm
  ### Feature description
  
  I was about to make a PR to improve the implementation of [insertion_sort algorithm](https://github.com/TheAlgorithms/Python/blob/master/sorts/insertion_sort.py) but since there might be multiple ways of doing so, I thought I should first ask your opinions.
  
  These are the things that need improvements:
  
  1. We unnecessarily create a whole new copy of the list: `enumerate(collection[1:])`.
  
     We can either use "indexes" to avoid this which is not very pythonic, or we can use the iterator of the list using `iter()` and throw away the first item using `next()`. In second case we have to either check for empty list first or wrap it in a try-except block. I'll go with indexes if you ask. What do you think?
  
  2. I think a function should either mutate the list in-place and returns `None`, or it should create new sorted list without modifying the original list. Mutating the list and returning the mutated list is not what most developers expect to see. What do you think?
  
  3. We can safely remove `if insert_index != temp_index:` condition and unindent its body. Assigning an item to an index of a list is not costly. So it's one less line in general.
  
  </issue>
  <code>
  [start of sorts/insertion_sort.py]
  1 """
  2 A pure Python implementation of the insertion sort algorithm
  3 
  4 This algorithm sorts a collection by comparing adjacent elements.
  5 When it finds that order is not respected, it moves the element compared
  6 backward until the order is correct.  It then goes back directly to the
  7 element's initial position resuming forward comparison.
  8 
  9 For doctests run following command:
  10 python3 -m doctest -v insertion_sort.py
  11 
  12 For manual testing run:
  13 python3 insertion_sort.py
  14 """
  15 
  16 
  17 def insertion_sort(collection: list) -> list:
  18     """A pure Python implementation of the insertion sort algorithm
  19 
  20     :param collection: some mutable ordered collection with heterogeneous
  21     comparable items inside
  22     :return: the same collection ordered by ascending
  23 
  24     Examples:
  25     >>> insertion_sort([0, 5, 3, 2, 2])
  26     [0, 2, 2, 3, 5]
  27     >>> insertion_sort([]) == sorted([])
  28     True
  29     >>> insertion_sort([-2, -5, -45]) == sorted([-2, -5, -45])
  30     True
  31     >>> insertion_sort(['d', 'a', 'b', 'e', 'c']) == sorted(['d', 'a', 'b', 'e', 'c'])
  32     True
  33     >>> import random
  34     >>> collection = random.sample(range(-50, 50), 100)
  35     >>> insertion_sort(collection) == sorted(collection)
  36     True
  37     >>> import string
  38     >>> collection = random.choices(string.ascii_letters + string.digits, k=100)
  39     >>> insertion_sort(collection) == sorted(collection)
  40     True
  41     """
  42 
  43     for insert_index, insert_value in enumerate(collection[1:]):
  44         temp_index = insert_index
  45         while insert_index >= 0 and insert_value < collection[insert_index]:
  46             collection[insert_index + 1] = collection[insert_index]
  47             insert_index -= 1
  48         if insert_index != temp_index:
  49             collection[insert_index + 1] = insert_value
  50     return collection
  51 
  52 
  53 if __name__ == "__main__":
  54     from doctest import testmod
  55 
  56     testmod()
  57 
  58     user_input = input("Enter numbers separated by a comma:\n").strip()
  59     unsorted = [int(item) for item in user_input.split(",")]
  60     print(f"{insertion_sort(unsorted) = }")
  61
  [end of sorts/insertion_sort.py]
  </code>
  
  I need you to solve this issue by generating a single patch file that I can apply directly to this repository using git apply. Please respond with a single patch file in the following format.
  <patch>
  diff --git a/file.py b/file.py
  --- a/file.py
  +++ b/file.py
  @@ -1,27 +1,35 @@
   def euclidean(a, b):
  -    while b:
  -        a, b = b, a % b
  -    return a
  +    if b == 0:
  +        return a
  +    return euclidean(b, a % b)
   
   
   def bresenham(x0, y0, x1, y1):
       points = []
       dx = abs(x1 - x0)
       dy = abs(y1 - y0)
  -    sx = 1 if x0 < x1 else -1
  -    sy = 1 if y0 < y1 else -1
  -    err = dx - dy
  +    x, y = x0, y0
  +    sx = -1 if x0 > x1 else 1
  +    sy = -1 if y0 > y1 else 1
   
  -    while True:
  -        points.append((x0, y0))
  -        if x0 == x1 and y0 == y1:
  -            break
  -        e2 = 2 * err
  -        if e2 > -dy:
  -            err -= dy
  -            x0 += sx
  -        if e2 < dx:
  -            err += dx
  -            y0 += sy
  +    if dx > dy:
  +        err = dx / 2.0
  +        while x != x1:
  +            points.append((x, y))
  +            err -= dy
  +            if err < 0:
  +                y += sy
  +                err += dx
  +            x += sx
  +    else:
  +        err = dy / 2.0
  +        while y != y1:
  +            points.append((x, y))
  +            err -= dx
  +            if err < 0:
  +                x += sx
  +                err += dy
  +            y += sy
  +
  +    points.append((x, y))
       return points
  
  </patch>
golden_diff: diff --git a/sorts/insertion_sort.py b/sorts/insertion_sort.py
  --- a/sorts/insertion_sort.py
  +++ b/sorts/insertion_sort.py
  @@ -13,8 +13,19 @@
   python3 insertion_sort.py
   """
   
  +from collections.abc import MutableSequence
  +from typing import Any, Protocol, TypeVar
   
  -def insertion_sort(collection: list) -> list:
  +
  +class Comparable(Protocol):
  +    def __lt__(self, other: Any, /) -> bool:
  +        ...
  +
  +
  +T = TypeVar("T", bound=Comparable)
  +
  +
  +def insertion_sort(collection: MutableSequence[T]) -> MutableSequence[T]:
       """A pure Python implementation of the insertion sort algorithm
   
       :param collection: some mutable ordered collection with heterogeneous
  @@ -40,13 +51,12 @@
       True
       """
   
  -    for insert_index, insert_value in enumerate(collection[1:]):
  -        temp_index = insert_index
  -        while insert_index >= 0 and insert_value < collection[insert_index]:
  -            collection[insert_index + 1] = collection[insert_index]
  +    for insert_index in range(1, len(collection)):
  +        insert_value = collection[insert_index]
  +        while insert_index > 0 and insert_value < collection[insert_index - 1]:
  +            collection[insert_index] = collection[insert_index - 1]
               insert_index -= 1
  -        if insert_index != temp_index:
  -            collection[insert_index + 1] = insert_value
  +        collection[insert_index] = insert_value
       return collection
  
verification_info: {"golden_diff": "diff --git a/sorts/insertion_sort.py b/sorts/insertion_sort.py\n--- a/sorts/insertion_sort.py\n+++ b/sorts/insertion_sort.py\n@@ -13,8 +13,19 @@\n python3 insertion_sort.py\n \"\"\"\n \n+from collections.abc import MutableSequence\n+from typing import Any, Protocol, TypeVar\n \n-def insertion_sort(collection: list) -> list:\n+\n+class Comparable(Protocol):\n+    def __lt__(self, other: Any, /) -> bool:\n+        ...\n+\n+\n+T = TypeVar(\"T\", bound=Comparable)\n+\n+\n+def insertion_sort(collection: MutableSequence[T]) -> MutableSequence[T]:\n     \"\"\"A pure Python implementation of the insertion sort algorithm\n \n     :param collection: some mutable ordered collection with heterogeneous\n@@ -40,13 +51,12 @@\n     True\n     \"\"\"\n \n-    for insert_index, insert_value in enumerate(collection[1:]):\n-        temp_index = insert_index\n-        while insert_index >= 0 and insert_value < collection[insert_index]:\n-            collection[insert_index + 1] = collection[insert_index]\n+    for insert_index in range(1, len(collection)):\n+        insert_value = collection[insert_index]\n+        while insert_index > 0 and insert_value < collection[insert_index - 1]:\n+            collection[insert_index] = collection[insert_index - 1]\n             insert_index -= 1\n-        if insert_index != temp_index:\n-            collection[insert_index + 1] = insert_value\n+        collection[insert_index] = insert_value\n     return collection\n", "issue": "improvement to insertion_sort algorithm\n### Feature description\r\n\r\nI was about to make a PR to improve the implementation of [insertion_sort algorithm](https://github.com/TheAlgorithms/Python/blob/master/sorts/insertion_sort.py) but since there might be multiple ways of doing so, I thought I should first ask your opinions.\r\n\r\nThese are the things that need improvements:\r\n\r\n1. We unnecessarily create a whole new copy of the list: `enumerate(collection[1:])`.\r\n\r\n   We can either use \"indexes\" to avoid this which is not very pythonic, or we can use the iterator of the list using `iter()` and throw away the first item using `next()`. In second case we have to either check for empty list first or wrap it in a try-except block. I'll go with indexes if you ask. What do you think?\r\n\r\n2. I think a function should either mutate the list in-place and returns `None`, or it should create new sorted list without modifying the original list. Mutating the list and returning the mutated list is not what most developers expect to see. What do you think?\r\n\r\n3. We can safely remove `if insert_index != temp_index:` condition and unindent its body. Assigning an item to an index of a list is not costly. So it's one less line in general.\nimprovement to insertion_sort algorithm\n### Feature description\r\n\r\nI was about to make a PR to improve the implementation of [insertion_sort algorithm](https://github.com/TheAlgorithms/Python/blob/master/sorts/insertion_sort.py) but since there might be multiple ways of doing so, I thought I should first ask your opinions.\r\n\r\nThese are the things that need improvements:\r\n\r\n1. We unnecessarily create a whole new copy of the list: `enumerate(collection[1:])`.\r\n\r\n   We can either use \"indexes\" to avoid this which is not very pythonic, or we can use the iterator of the list using `iter()` and throw away the first item using `next()`. In second case we have to either check for empty list first or wrap it in a try-except block. I'll go with indexes if you ask. What do you think?\r\n\r\n2. I think a function should either mutate the list in-place and returns `None`, or it should create new sorted list without modifying the original list. Mutating the list and returning the mutated list is not what most developers expect to see. What do you think?\r\n\r\n3. We can safely remove `if insert_index != temp_index:` condition and unindent its body. Assigning an item to an index of a list is not costly. So it's one less line in general.\n", "before_files": [{"content": "\"\"\"\nA pure Python implementation of the insertion sort algorithm\n\nThis algorithm sorts a collection by comparing adjacent elements.\nWhen it finds that order is not respected, it moves the element compared\nbackward until the order is correct.  It then goes back directly to the\nelement's initial position resuming forward comparison.\n\nFor doctests run following command:\npython3 -m doctest -v insertion_sort.py\n\nFor manual testing run:\npython3 insertion_sort.py\n\"\"\"\n\n\ndef insertion_sort(collection: list) -> list:\n    \"\"\"A pure Python implementation of the insertion sort algorithm\n\n    :param collection: some mutable ordered collection with heterogeneous\n    comparable items inside\n    :return: the same collection ordered by ascending\n\n    Examples:\n    >>> insertion_sort([0, 5, 3, 2, 2])\n    [0, 2, 2, 3, 5]\n    >>> insertion_sort([]) == sorted([])\n    True\n    >>> insertion_sort([-2, -5, -45]) == sorted([-2, -5, -45])\n    True\n    >>> insertion_sort(['d', 'a', 'b', 'e', 'c']) == sorted(['d', 'a', 'b', 'e', 'c'])\n    True\n    >>> import random\n    >>> collection = random.sample(range(-50, 50), 100)\n    >>> insertion_sort(collection) == sorted(collection)\n    True\n    >>> import string\n    >>> collection = random.choices(string.ascii_letters + string.digits, k=100)\n    >>> insertion_sort(collection) == sorted(collection)\n    True\n    \"\"\"\n\n    for insert_index, insert_value in enumerate(collection[1:]):\n        temp_index = insert_index\n        while insert_index >= 0 and insert_value < collection[insert_index]:\n            collection[insert_index + 1] = collection[insert_index]\n            insert_index -= 1\n        if insert_index != temp_index:\n            collection[insert_index + 1] = insert_value\n    return collection\n\n\nif __name__ == \"__main__\":\n    from doctest import testmod\n\n    testmod()\n\n    user_input = input(\"Enter numbers separated by a comma:\\n\").strip()\n    unsorted = [int(item) for item in user_input.split(\",\")]\n    print(f\"{insertion_sort(unsorted) = }\")\n", "path": "sorts/insertion_sort.py"}]}