<commit_before>"""
                Insertion Sort:
                ---------------

Basics:
-------

    The insertion sort, although still O(n^2), works in a slightly different
way. It always maintains a sorted sublist in the lower positions of the list.
Each new Item is then "inserted" back into the previous sublist such that the
sorted sublist is one item larger.

Logic:
------

    We begin by assuming that a list with one item (position 0) is already
sorted. On each pass, one for each item 1 through n-1, the current item is
checked against those in the already sorted sublist.

    As we look back into th already sorted sublist, we shift those items that
are greater to the right. When we reach a smaller item or the end of the
sublist, the current item can be inserted.

Big O:
------

O(n^2)
"""
from BubbleSort import randomList

def insertionSort(alist):
    for index in range(1, len(alist)):

        currentvalue = alist[index]
        position = index

        while position>0 and alist[position -1] >currentvalue:
            alist[position] = alist[position-1]<commit_msg>added a comment<commit_after>"""
                Insertion Sort:
                ---------------

Basics:
-------

    The insertion sort, although still O(n^2), works in a slightly different
way. It always maintains a sorted sublist in the lower positions of the list.
Each new Item is then "inserted" back into the previous sublist such that the
sorted sublist is one item larger.

Logic:
------

    We begin by assuming that a list with one item (position 0) is already
sorted. On each pass, one for each item 1 through n-1, the current item is
checked against those in the already sorted sublist.

    As we look back into th already sorted sublist, we shift those items that
are greater to the right. When we reach a smaller item or the end of the
sublist, the current item can be inserted.

Big O:
------

O(n^2)
"""
from BubbleSort import randomList

def insertionSort(alist):
    """
    A basic insertion sort
    """
    for index in range(1, len(alist)):

        currentvalue = alist[index]
        position = index

        while position>0 and alist[position -1] >currentvalue:
            alist[position] = alist[position-1]
{'fraction_non_alphanumeric': 0.08859060402684564, 'fraction_numerical': 0.008053691275167786, 'mean_word_length': 2.6595744680851063, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2750788', 'n_tokens_mistral': 623, 'n_tokens_neox': 599, 'n_words': 305}