Insertion Sort

Tip

• Useful if total number of items to sort is low.
• Also look at Outout section for better understanding.
• You may also read - https://en.wikipedia.org/wiki/Insertion_sort

Example

"""Insertion Sort"""

def sort_items(items: list) -> list:
    print("Processing - ", items)
    # If total items are one or less, we simply return it back
    if len(items) > 1:
        j = 1

        # We start comparing the value of the second item (index is 1 for the second item) with previous ones
        # Items on left of `j` index are always sorted
        for key in items[1:]:
            print(items[:j], key)
            i = j - 1

            # We iterate over each item with lower index, until key is higher than it
            while i >= 0 and key < items[i]:
                # As we move down the comparison, we shift values of the indices upwards
                items[i + 1] = items[i]

                # and then continue comparison with lower indices
                i -= 1

            # In the end we replace the value of `key` to index higher than whose value is greater than `key`
            # Since we already moved remaining values up, we are good with it
            items[i + 1] = key

            j += 1

    print(items)
    return items


if __name__ == '__main__':
    assert sort_items([]) == []
    assert sort_items([1]) == [1]
    assert sort_items([4, 3, 5, 2, 1, 0]) == [0, 1, 2, 3, 4, 5]

Output

Processing -  []
[]
Processing -  [1]
[1]
Processing -  [4, 3, 5, 2, 1, 0]
[4] 3
[3, 4] 5
[3, 4, 5] 2
[2, 3, 4, 5] 1
[1, 2, 3, 4, 5] 0
[0, 1, 2, 3, 4, 5]