<jupyter_start><jupyter_text>Chapter Two - Getting Started Insertion SortThe insertion sort is a strategy for sorting an array by iterating over each item in the array and shifting it in one direction until it satisfies a greater-than or less-than condition. To put it another way, we will have two loops: one that iterates over all the values in an array that we want to sort, and a loop inside that loop that compares one value to all the values to the left, then decides where to put it.In pseudocode, this looks something like:```initialize an outer index for iterating over values in the arraywhile outer index is less than the length of the whole array  initialize value at outer index  initialize a searching index that starts to the left of outer index  while the value at the searching index is less than the value at the outer index    shift the value at the searching index one place to the right    shift the outer index one place to the left  insert the value at the outer index one place to the right of the search index  shift the outer index one place to the right```In Python, it can be written:<jupyter_code>def insertion_sort(array):
    item_ix = 1
    while item_ix < len(array):
        item_value = array[item_ix]
        search_ix = item_ix - 1
        while (search_ix >= 0) and (item_value < array[search_ix]):
            array[search_ix + 1] = array[search_ix]
            search_ix -= 1
        array[search_ix + 1] = item_value
        item_ix += 1
    return array<jupyter_output><empty_output><jupyter_text>We can test this to make sure it's working with a random sequence of integers<jupyter_code>from numpy import random
insertion_sort(random.randint(0,100,10))<jupyter_output><empty_output><jupyter_text>Merge sortThe insertion sort works pretty well with small arrays, but the amount of time it takes to sort an array increases exponentially. To sort more quickly, we can use a recursive algorithm that sorts arrays by splitting them up into smaller and smaller pieces, ordering them, and recombining them. The crucial step here is the recombining step, as this is where the merge sort gets its computational efficiency.In pseudocode, we might write this like:```divide array into a left array and right arraywhile each array is longer than longer than one  call this function recursively to sort theminitialize separate indices for the array, and its left and right piecesfor each position in the array  put the smaller of the left or right arrays item at their respective indices  increment the index for the array that gave the value```To make this work in Python, we need to do two things. First, we need to import a function that copies mutable objects. By default, when Python initializes a mutable object, it creates a place in memory and all assignment statements that reference that object are just pointing to the location in memory. This means that if you assign two names to the same mutable object, changing one will change the other as well:<jupyter_code>a = [1, 2, 3]
b = a
del a[0]
b<jupyter_output><empty_output><jupyter_text>To make a different copy of an object in memory, so that we can operate on one while not changing the other, we will import a function called `deepcopy`.<jupyter_code>from copy import deepcopy

a = [1, 2, 3]
b = deepcopy(a)
del a[0]
b<jupyter_output><empty_output><jupyter_text>The other thing we'll need to do is define a function that returns something other than an exception when we try to access an item in an array past the last index of the array. The reason for this is that after one sub-array has run out of items to put back into the main array, it still has to give something to serve in the comparison between the left and right sub-arrays. Here, we are going to have it return `infinity` to facilitate a `less than` comparison.<jupyter_code>def get_value(array, ix):
    try:
        value = array[ix]
    except IndexError:
        value = float('inf')
    return value<jupyter_output><empty_output><jupyter_text>Now, we can transcribe our pseudocode into Python:<jupyter_code>def merge_sort(array):
    left_array = deepcopy(array[:(len(array)//2)])
    right_array = deepcopy(array[(len(array)//2):])
    if len(left_array) > 1:
        left_array = merge_sort(left_array)
    if len(right_array) > 1:
        right_array = merge_sort(right_array)
    left_ix = 0
    right_ix = 0
    array_ix = 0
    while array_ix < len(array):
        left_value = get_value(left_array, left_ix)
        right_value = get_value(right_array, right_ix)
        if left_value < right_value:
            array[array_ix] = left_value
            left_ix += 1
        else:
            array[array_ix] = right_value
            right_ix += 1
        array_ix += 1
    return array<jupyter_output><empty_output><jupyter_text>And as a sanity check, we have it sort a short list for us:<jupyter_code>merge_sort(random.randint(0,100,10))<jupyter_output><empty_output><jupyter_text>At small sizes, insert sort is faster than merge<jupyter_code>%timeit insertion_sort(random.randint(0,100,100))
%timeit merge_sort(random.randint(0,100,100))<jupyter_output>1000 loops, best of 3: 1.61 ms per loop<jupyter_text>But at large sizes, merge_sort greatly outperforms insertion:<jupyter_code>%timeit insertion_sort(random.randint(0,100,10000))
%timeit merge_sort(random.randint(0,100,10000))<jupyter_output>1 loops, best of 3: 212 ms per loop<jupyter_text>Combining sort strategiesIf we want to make an even faster, algorithm, we can combine these two strategies where the sort type used is dependent on the size of the array. But what size should we pick? We know that insertion sort is going to scale exponentially compared to merge sort, so we can make a guess that they'll converge around an n of 200.<jupyter_code>%timeit insertion_sort(random.randint(0,100,200))
%timeit merge_sort(random.randint(0,100,200))<jupyter_output>100 loops, best of 3: 4.21 ms per loop<jupyter_text>That's pretty close, so let's try it in our combined algorithm:<jupyter_code>def combined_sort(array):
    left_array = deepcopy(array[:(len(array)//2)])
    right_array = deepcopy(array[(len(array)//2):])
    if len(left_array) > 200:
        left_array = merge_sort(left_array)
    else:
        left_array = insertion_sort(left_array)
    if len(right_array) > 200:
        right_array = merge_sort(right_array)
    else:
        right_array = insertion_sort(right_array)
    left_ix = 0
    right_ix = 0
    array_ix = 0
    while array_ix < len(array):
        left_value = get_value(left_array, left_ix)
        right_value = get_value(right_array, right_ix)
        if left_value < right_value:
            array[array_ix] = left_value
            left_ix += 1
        else:
            array[array_ix] = right_value
            right_ix += 1
        array_ix += 1
    return array<jupyter_output><empty_output><jupyter_text>Again, as a sanity check, we can call this on a small array:<jupyter_code>combined_sort(random.randint(0,100,10))<jupyter_output><empty_output><jupyter_text>And we can benchmark it against the other two sort methods:<jupyter_code>%timeit combined_sort(random.randint(0,100,10000))<jupyter_output>1 loops, best of 3: 211 ms per loop<jupyter_text>Interestingly, the way we have it coded here, this doesn't speed up the processing by that much. It's probable that, in Python, the additional communication cost of calling insertion sort and passing data to it are outweighing the efficiency gains of using insertion sort at small array sizes.We can compare this to Python's base implementation of sort, called [timsort](http://svn.python.org/view/python/trunk/Objects/listsort.txt?revision=69846&view=markup):<jupyter_code>%timeit sorted(random.randint(0,100,10000))<jupyter_output>100 loops, best of 3: 3.63 ms per loop
{'fraction_non_alphanumeric': 0.06877967406646991, 'fraction_numerical': 0.020659566277428463, 'mean_word_length': 4.298436437797417, 'pattern_counts': {'":': 0, '<': 58, '<?xml version=': 0, '>': 57, '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}}
{'chain_length': '14', 'dir': 'jupyter-structured-clean-dedup', 'id': '582540', 'license': 'BSD-2-Clause', 'n_tokens_mistral': 2400, 'n_tokens_neox': 2247, 'n_words': 935, 'path': 'chapter_02.ipynb', 'repo_name': 'deniederhut/intro-to-algorithms', 'size': '7793'}