We are currently solving the following issue within our repository. Here is the issue text:
--- BEGIN 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.

--- END ISSUE ---

Below are some code segments, each from a relevant file. One or more of these files may contain bugs.
--- BEGIN FILES ---
Path: `sorts/insertion_sort.py`
Content:
```
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 FILES ---

Please first localize the bug based on the issue statement, and then generate a patch according to the `git diff` format fenced by three backticks.

Here is an example:

```diff
diff --git a/examples/server_async.py b/examples/server_async.py
--- a/examples/server_async.py
+++ b/examples/server_async.py
@@ -313,4 +313,4 @@
 
 
 if __name__ == "__main__":
-    asyncio.run(run_async_server("."), debug=True)
+    asyncio.run(run_async_server(), debug=True)
diff --git a/examples/server_sync.py b/examples/server_sync.py
--- a/examples/server_sync.py
+++ b/examples/server_sync.py
@@ -313,5 +313,5 @@
 
 
 if __name__ == "__main__":
-    server = run_sync_server(".")
+    server = run_sync_server()
     server.shutdown()

```

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

{"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"}], "after_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\nfrom collections.abc import MutableSequence\nfrom typing import Any, Protocol, TypeVar\n\n\nclass Comparable(Protocol):\n    def __lt__(self, other: Any, /) -> bool:\n        ...\n\n\nT = TypeVar(\"T\", bound=Comparable)\n\n\ndef 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    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 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        collection[insert_index] = 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"}]}