The Mergesort

# python
from functools import partial

# pypi
from numba import njit
from joblib import Parallel, delayed

from numpy.random import default_rng

import altair
import numpy
import pandas

# this project
from bowling.sort.insertion import insertion_sort

from graeae import Timer
from graeae.visualization.altair_helpers import output_path, save_chart

numba_random = default_rng(2022)
TIMER = Timer()

SLUG = "the-mergesort"
OUTPUT_PATH = output_path(SLUG)
save_it = partial(save_chart, output_path=OUTPUT_PATH)

def merger(thing_to_sort) -> tuple:
    """A thing to add the size of the input to the output

    Args:
     thing_to_sort: collection of items to sort

    Returns:
     number of things to sort, count of merges
    """
    return len(thing_to_sort), mergesort(thing_to_sort)

ninsertion = njit(insertion_sort)

things_to_sort = [numba_random.integers(low=0, high=count, size=count)
                  for count in range(1, 10**5 + 1, 1000)]

with TIMER:
    insertion_output = Parallel(n_jobs=-1)(
        delayed(ninsertion)(thing_to_sort)
        for thing_to_sort in things_to_sort)

with TIMER:
    merge_output = Parallel(n_jobs=-1)(
        delayed(merger)(thing_to_sort)
        for thing_to_sort in things_to_sort)

SIZE, COMPARISONS = 0, 1
unzipped = list(zip(*merge_output))
frame = pandas.DataFrame({"Size": unzipped[SIZE],
"Mergesort": unzipped[COMPARISONS]})

unzipped = list(zip(*insertion_output))
frame["Insertion Sort"] = unzipped[COMPARISONS]

melted = frame.melt(id_vars=["Size"],
                    value_vars=["Mergesort", "Insertion Sort"],
                    var_name="Sort Algorithm", value_name="Comparisons")

chart = altair.Chart(melted).mark_point().encode(
    x="Size",
    y="Comparisons",
    color="Sort Algorithm",
    tooltip=[altair.Tooltip("Size", format=","),
             altair.Tooltip("Comparisons", format=","),
             "Sort Algorithm"]
).properties(
    title="Insertion vs Merge Sort",
    width=800,
    height=525,
)

save_it(chart, "insertion-vs-merge")

frame["nlog2(n)"] = frame["Size"] * numpy.log2(frame["Size"])
del(frame["Insertion Sort"])
melted = frame.melt(id_vars=["Size"],
                    value_vars=["Mergesort", "nlog2(n)"],
                    var_name="Source", value_name="Comparisons")

chart = altair.Chart(melted).mark_point().encode(
    x="Size",
    y="Comparisons",
    color="Source",
    tooltip=[altair.Tooltip("Size", format=","),
             altair.Tooltip("Comparisons", format=","),
             "Source"]
).properties(
    title="Merge Sort vs Theoretical",
    width=800,
    height=525,
)

save_it(chart, "merge-by-logn")

from bowling.sort.merge import merge_clrs

def mergesort_tracer(collection: MutableSequence, left: int, right: int,
                     tracer: dict=None) -> dict:
    """Sorts the collection using a recursive mergesort

    This uses the CLRS merge-sort to build dict of the locations of the
    elements as the merging is done

    Args:
     collection: a mutable sequence
     left: the index of the beginning element of the sub-array
     right: the index of the ending element of the sub-array
     tracer: the dictionary to track the indices of the items

    Returns:
     tracer updated with post-merge locations of the items in tracer
    """
    if tracer is None:
        tracer = {element: [index] for index, element in enumerate(collection)}

    if left < right:
        middle = (left + right)//2
        mergesort_tracer(collection, left, middle, tracer)
        mergesort_tracer(collection, middle + 1, right, tracer)
        merge_clrs(collection, left, middle, right)

        for index, element in enumerate(collection):
            tracer[element].append(index)
    return tracer