Insertion sort in Python with list history. https://neetcode.io/problems/insertionSort

insertionSort.py

from typing import List
from collections import namedtuple

Pair = namedtuple('Pair', ['key', 'value'])

# Definition for a pair.
# class Pair:
#     def __init__(self, key: int, value: str):
#         self.key = key
#         self.value = value
class Solution:
    def insertionSort(self, pairs: List[Pair]) -> List[List[Pair]]:
        history = [pairs.copy()] if pairs else []
        sorted_pairs = pairs

        for i in range(0, len(sorted_pairs) - 1):
            a = sorted_pairs[i].key
            b = sorted_pairs[i+1].key

            j = i
            while b < a and j > -1:
                # Swap positions.
                temp = sorted_pairs[j+1]
                sorted_pairs[j+1] = sorted_pairs[j]
                sorted_pairs[j] = temp

                a = sorted_pairs[j - 1].key
                b = sorted_pairs[j].key

                j = j - 1

            history.append(sorted_pairs.copy())

        return history

zclient.py

client = Solution()
result = client.insertionSort([Pair(3, "cat"), Pair(3, "bird"), Pair(2, "dog")])
print(result)