Python Sorting Algorithms : (TimSort + Introspective Sort + bogo Sort + pancake Sort + Insertion Sort + Binary Insertion Sort + Count Sort + Merge Sort + Quick Sort + Bubble Sort)

Python Sorting Algorithms.py

import bisect
import heapq
import inspect
from random import randint, shuffle
from statistics import mean
from timeit import default_timer, repeat

import matplotlib.pyplot as plt
from bigO import bigO
from win10toast import ToastNotifier

'''
def runAlgorithm(algorithm, array, timeResults):
    setup_code = f"from __main__ import {algorithm}" if algorithm != "sorted" else ""

    stmt = f"{algorithm}({array})"

    times = repeat(setup=setup_code, stmt=stmt, repeat=3, number=5)
    timeResults[algorithm] = round(min(times), 5)

    print(f"def: {algorithm}(), Execution time: {mean(times)/5:.5f}초")


def runAlgorithm2(algorithm, array, timeResults):
    # result
    tot = 0.0
    #print("Before:", array)
    t0 = default_timer()
    if algorithm == "sorted":
        result = list(sorted(array))
    else:
        result = globals()[algorithm](array)
    t1 = default_timer()
    #print("After:", result)
    print(f"{algorithm}() Sorting Result : {list(sorted(array)) ==  result}")
    tot += (t1-t0)

    timeResults[algorithm] = round(tot, 5)
    print(f"def: {algorithm}(), Execution Time: {tot:.5f}s")
'''


def runAlgorithm3(algorithm, array, timeResults):
    lib = bigO.bigO()

    # print("Before sorting", array)

    testArray = array.copy()
    time, result = lib.runtime(algorithm, testArray, epoch=3, prtResult=False)

    print(f"{algorithm.__name__}(array) Sorting Result : {sorted(testArray) ==  result}")
    # print("After sorting", result)

    timeResults[algorithm] = round(time, 5)

    
def binarySearch(array, item, start, end):
    if start == end:
        if array[start] > item:
            return start
        else:
            return start + 1
    if start > end:
        return start

    mid = (start + end) // 2

    if array[mid] < item:
        return binarySearch(array, item, mid + 1, end)

    elif array[mid] > item:
        return binarySearch(array, item, start, mid - 1)
    else:
        return mid


def bubbleSort(array):  # in-place | stable
    """
    Best : O(n) | O(1) Space
    Average : O(n^2) | O(1) Space
    Worst : O(n^2) | O(1) Space
    """
    isSorted = False
    counter = 0
    n = len(array) - 1
    while not isSorted:
        isSorted = True
        for i in range(n - counter):
            if array[i] > array[i + 1]:
                array[i], array[i + 1] = array[i + 1], array[i]
                isSorted = False
                
        counter += 1

    return array


def binaryInsertSort(array):
    for index in range(1, len(array)):
        value = array[index]
        pos = binarySearch(array, value, 0, index - 1)
        array = array[:pos] + [value] + \
            array[pos:index] + array[index + 1:]
    return array


def insertSort(array, begin=0, end=None):  # in-place | stable
    '''
    Best O(n) Time | O(1) Space
    Average O(n^2) Time | O(1) Space
    Worst (On^2) Time | O(1) Space
    '''
    if end == None:
        end = len(array)
    for i in range(begin, end):
        j = i
        toChange = array[i]
        while (j != begin and array[j - 1] > toChange):
            array[j] = array[j - 1]
            j -= 1
        array[j] = toChange
    return array


def gnomeSort(array):  # in-place | stable
    '''
    Best : O(n) Time | O(1) Space
    Average : O(n^2) Time | O(1) Space
    Worst : O(n^2) Time | O(1) Space
    '''
    index = 0
    while index < len(array):
        if index == 0 or array[index] >= array[index - 1]:
            index += 1
        else:
            array[index], array[index-1] = array[index-1], array[index]
            index -= 1

    return array


def pancakeSort(array):  # in-place | not-stable
    # O(n^2) Time | O(N) Space
    if len(array) <= 1:
        return array
    for cur in range(len(array), 1, -1):
        # Finding index of maximum number in arr
        index_max = array.index(max(array[0:cur]))
        if index_max+1 != cur:
            # Needs moving
            if index_max != 0:
                # reverse from 0 to index_max
                array[:index_max+1] = reversed(array[:index_max+1])
            # Reverse list
            array[:cur] = reversed(array[:cur])
    return array


def bogoSort(array):  # in-place
    """
    Best Case Complexity: O(n)
    Average Case Complexity: O(n(n-1)!)
    Worst Case Complexity: O(∞)
    """
    
    n = len(array)
    
    def is_sorted(array):
        i = 0
        while i+1 < n:
            if array[i] > array[i+1]:
                return False
            i += 1
        return True

    while not is_sorted(array):
        shuffle(array)

    return array


def smoothSort(array):  # in-place | not-stable
    # O(n) Time | O(n) Space
    def numbersLeonardo(size):
        numbers = [1, 1]
        nextNumber = numbers[-1] + numbers[-2] + 1
        while len(numbers) >= 2 and size > nextNumber:
            numbers.append(nextNumber)
            nextNumber = numbers[-1] + numbers[-2] + 1
        numbers.reverse()
        return numbers

    def arrToHeap(data):
        leonardoNumbers = numbersLeonardo(len(data))
        listHeaps = []
        m = 0
        for i in leonardoNumbers:
            if len(data) - m >= i:
                listHeaps.append(data[m: m+i])
                m += i
        for i in listHeaps:
            heapq.heapify(i)

        listHeaps.reverse()
        return listHeaps

    def countIndexes(i, indexes):
        indexes.append(2*indexes[i]+1)
        indexes.append(2*indexes[i]+2)

        return indexes

    def getList(indexPart, heap):
        heapPart = []
        for i in indexPart:
            if i < len(heap):
                heapPart.append(heap[i])

        return heapPart

    def heapDivision(heap):
        heapleft = []
        heapright = []
        index = 0
        indexesLeft = [1]
        indexesRight = [2]
        while indexesLeft[-1] < len(heap):

            indexesLeft = countIndexes(index, indexesLeft)

            indexesRight = countIndexes(index, indexesRight)

            index += 1

        heapleft = getList(indexesLeft, heap)
        heapright = getList(indexesRight, heap)

        return heapleft, heapright

    listHeaps = arrToHeap(array)
    result = []
    heapLeft, heapRight = 0, 0

    while (listHeaps):
        flag = 0
        minIndex = listHeaps.index(min(listHeaps))
        currentRoot = listHeaps[0][0]
        currentMin = listHeaps[minIndex][0]
        heapq.heapreplace(listHeaps[0], currentMin)
        heapq.heapreplace(listHeaps[minIndex], currentRoot)
        if len(listHeaps[0]) > 1:
            heapLeft, heapRight = heapDivision(listHeaps[0])
            flag = 1
        minimum = heapq.heappop(listHeaps[0])
        result.append(minimum)
        listHeaps.pop(0)
        if flag == 1:
            listHeaps.insert(0, heapLeft)
            listHeaps.insert(0, heapRight)
    return result


def countSort(arr):  # stable
    # Time Complexity : O(n) | Space Complexity : O(n)
    minValue = min(arr)
    maxValue = max(arr) - minValue

    buckets = [0 for x in range(maxValue + 1)]

    for i in arr:
        buckets[i - minValue] += 1

    index = 0
    for i in range(len(buckets)):
        while buckets[i] > 0:
            arr[index] = i + minValue
            index += 1
            buckets[i] -= 1

    return arr


def quickSort(array):  # in-place | not-stable
    '''
    Best : O(nlogn) Time | O(logn) Space
    Average : O(nlogn) Time | O(logn) Space
    Worst : O(n^2) Time | O(logn) Space
    '''
    if len(array) <= 1:
        return array
    smaller, equal, larger = [], [], []
    pivot = array[randint(0, len(array)-1)]
    for x in array:
        if x < pivot:
            smaller.append(x)
        elif x == pivot:
            equal.append(x)
        else:
            larger.append(x)
    return quickSort(smaller)+equal+quickSort(larger)


def heapSort(arr):  # in-place | not-stable
    # Time Complexity O(nlogn) | Space Complexity O(1)

    def heapify(arr, n, i):  # Max Heap
        largest = i  # 트리에서 가장 큰 값 찾기
        l = 2 * i + 1  # Left Node
        r = 2 * i + 2  # Right Node

        if l < n and arr[i] < arr[l]:
            largest = l

        if r < n and arr[largest] < arr[r]:
            largest = r

        # root가 최대가 아니면
        # 최대 값과 바꾸고, 계속 heapify
        if largest != i:
            arr[i], arr[largest] = arr[largest], arr[i]
            heapify(arr, n, largest)

    n = len(arr)

    for i in range(n // 2, -1, -1):
        heapify(arr, n, i)

    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]
        # Heapify root element
        heapify(arr, i, 0)

    return arr


def heapSort2(iterable):  # in-place | not-stable
    # Time Complexity O(nlogn)
    # Using Python source at
    # https://github.com/python/cpython/blob/975d10a4f8f5d99b01d02fc5f99305a86827f28e/Lib/heapq.py

    def heappop(heap):
        """Pop the smallest item off the heap, maintaining the heap invariant."""
        lastelt = heap.pop()  # raises appropriate IndexError if heap is empty
        if heap:
            returnitem = heap[0]
            heap[0] = lastelt
            _siftup(heap, 0)
            return returnitem
        return lastelt

    def _siftup(heap, pos):
        endpos = len(heap)
        startpos = pos
        newitem = heap[pos]
        # Bubble up the smaller child until hitting a leaf.
        childpos = 2 * pos + 1  # leftmost child position
        while childpos < endpos:
            # Set childpos to index of smaller child.
            rightpos = childpos + 1
            if rightpos < endpos and not heap[childpos] < heap[rightpos]:
                childpos = rightpos
            # Move the smaller child up.
            heap[pos] = heap[childpos]
            pos = childpos
            childpos = 2 * pos + 1
        # The leaf at pos is empty now.  Put newitem there, and bubble it up
        # to its final resting place (by sifting its parents down).
        heap[pos] = newitem
        _siftdown(heap, startpos, pos)

    def _siftdown(heap, startpos, pos):
        newitem = heap[pos]
        # Follow the path to the root, moving parents down until finding a place
        # newitem fits.
        while pos > startpos:
            parentpos = (pos - 1) >> 1
            parent = heap[parentpos]
            if newitem < parent:
                heap[pos] = parent
                pos = parentpos
                continue
            break
        heap[pos] = newitem

    def heapify(x):
        """Transform list into a heap, in-place, in O(len(x)) time."""
        n = len(x)
        # Transform bottom-up.  The largest index there's any point to looking at
        # is the largest with a child index in-range, so must have 2*i + 1 < n,
        # or i < (n-1)/2.  If n is even = 2*j, this is (2*j-1)/2 = j-1/2 so
        # j-1 is the largest, which is n//2 - 1.  If n is odd = 2*j+1, this is
        # (2*j+1-1)/2 = j so j-1 is the largest, and that's again n//2-1.
        for i in reversed(range(n // 2)):
            _siftup(x, i)

        return x

    h = heapify(iterable)

    return [heappop(h) for _ in range(len(h))]


def mergeSort(array):  # stable
    """
    Best : O(nlogn) Time | O(n) Space
    Average : O(nlogn) Time | O(n) Space
    Worst : O(nlongn) Time | O(n) Space
    """

    def mergeHelper(main, startIdx, endIdx, aux):
        if startIdx == endIdx:
            return
        middleIdx = (startIdx + endIdx) // 2
        mergeHelper(aux, startIdx, middleIdx, main)
        mergeHelper(aux, middleIdx + 1, endIdx, main)
        merge(main, startIdx, middleIdx, endIdx, aux)

    def merge(main, startIdx, middleIdx, endIdx, aux):
        k = startIdx
        i = startIdx
        j = middleIdx + 1
        while i <= middleIdx and j <= endIdx:
            if aux[i] <= aux[j]:
                main[k] = aux[i]
                i += 1
            else:
                main[k] = aux[j]
                j += 1
            k += 1

        while i <= middleIdx:
            main[k] = aux[i]
            i += 1
            k += 1
        while j <= endIdx:
            main[k] = aux[j]
            j += 1
            k += 1

    if len(array) <= 1:
        return array

    aux = array[:]
    mergeHelper(array, 0, len(array) - 1, aux)
    return array


def introSort(array):  # in-place | not-stable
    # Time Complexity O(nlogn) | Space Complexity O(logn)
    maxDepth = 2 * (len(array).bit_length() - 1)
    sizeThreshold = 16
    return introSortHelper(array, 0, len(array), sizeThreshold, maxDepth)


def introSortHelper(array, start, end, sizeThreshold, depthLimit):
    def medianOf3(array, lowIdx, midIdx, highIdx):
        if (array[lowIdx] - array[midIdx]) * (array[highIdx] - array[lowIdx]) >= 0:
            return array[lowIdx]

        elif (array[midIdx] - array[lowIdx]) * (array[highIdx] - array[midIdx]) >= 0:
            return array[midIdx]

        else:
            return array[highIdx]

    def getPartition(array, low, high, pivot):
        i = low
        j = high
        while True:

            while (array[i] < pivot):
                i += 1
            j -= 1
            while (pivot < array[j]):
                j -= 1
            if i >= j:
                return i
            array[i], array[j] = array[j], array[i]
            i += 1

    while(end - start > sizeThreshold):
        if depthLimit == 0:
            return heapSort(array)
        depthLimit -= 1

        median = medianOf3(array, start, start +
                           ((end - start) // 2) + 1, end - 1)
        p = getPartition(array, start, end, median)
        introSortHelper(array, p, end, sizeThreshold, depthLimit)
        end = p

    return insertSort(array, start, end)


def timSort(lst):
    """
    Python sort(), sorted() implementation
    from https://github.com/hu-ng/timsort/blob/master/timsort.py
    
    Best : O(n) Time | O(n) Space
    Average : O(nlogn) Time | O(n) Space
    Worst : O(nlogn) Time | O(n) Space
    """

    def reverse(lst, s, e):
        """Reverse the order of a list in place
        Input: s = starting index, e = ending index"""
        while s < e and s != e:
            lst[s], lst[e] = lst[e], lst[s]
            s += 1
            e -= 1

    def make_temp_array(lst, s, e):
        """From the lst given, make a copy from index s to index e"""
        array = []
        while s <= e:
            array.append(lst[s])
            s += 1
        return array

    def merge_compute_minrun(n):
        """Returns the minimum length of a run from 23 - 64 so that
        the len(array)/minrun is less than or equal to a power of 2."""
        r = 0
        while n >= 32:
            r |= n & 1
            n >>= 1
        return n + r

    def count_run(lst, s_run):
        """Count the length of one run, returns starting/ending indices,
        a boolean value to present increasing/decreasing run,
        and the length of the run"""
        increasing = True

        # If count_run started at the final position of the array
        if s_run == len(lst) - 1:
            return [s_run, s_run, increasing, 1]
        else:
            e_run = s_run
            # Decreasing run (strictly decreasing):
            if lst[s_run] > lst[s_run + 1]:
                while lst[e_run] > lst[e_run + 1]:
                    e_run += 1
                    if e_run == len(lst) - 1:
                        break
                increasing = False
                return [s_run, e_run, increasing, e_run - s_run + 1]

            # Increasing run (non-decreasing):
            else:
                while lst[e_run] <= lst[e_run + 1]:
                    e_run += 1
                    if e_run == len(lst) - 1:
                        break
                return [s_run, e_run, increasing, e_run - s_run + 1]

    def bin_sort(lst, s, e, extend):
        """Binary insertion sort, assumed that lst[s:e + 1] is sorted.
        Extend the run by the number indicated by 'extend'"""

        for i in range(1, extend + 1):
            pos = 0
            start = s
            end = e + i

            # Value to be inserted
            value = lst[end]

            # If the value is already bigger than the last element from start -> end:
            # Don't do the following steps
            if value >= lst[end - 1]:
                continue

            # While-loop does the binary search
            while start <= end:
                if start == end:
                    if lst[start] > value:
                        pos = start
                        break
                    else:
                        pos = start + 1
                        break
                mid = (start + end) // 2
                if value >= lst[mid]:
                    start = mid + 1
                else:
                    end = mid - 1

            if start > end:
                pos = start

            # 'Push' the elements to the right by 1 element
            # Copy the value back the right position.
            for x in range(e + i, pos, -1):
                lst[x] = lst[x - 1]
            lst[pos] = value

    def gallop(lst, val, low, high, ltr):
        """Find the index of val in the slice[low:high]"""

        if ltr == True:
            # Used for merging from left to right
            # The index found will be so that every element prior
            # to that index is strictly smaller than val
            pos = bisect.bisect_left(lst, val, low, high)
            return pos

        else:
            # Used for merging from right to left
            # The index found will be so that every element from
            # that index onwards is strictly larger than val
            pos = bisect.bisect_right(lst, val, low, high)
            return pos

    def merge(lst, stack, run_num):
        """Merge the two runs and update the remaining runs in the stack
        Only consequent runs are merged, one lower, one upper."""

        # Make references to the to-be-merged runs
        run_a = stack[run_num]
        run_b = stack[run_num + 1]

        # Make a reference to where the new combined run would be.
        new_run = [run_a[0], run_b[1], True, run_b[1] - run_a[0] + 1]

        # Put this new reference in the correct position in the stack
        stack[run_num] = new_run

        # Delete the upper run of the two runs from the stack
        del stack[run_num + 1]

        # If the length of run_a is smaller than or equal to length of run_b
        if run_a[3] <= run_b[3]:
            merge_low(lst, run_a, run_b, 7)

        # If the length of run_a is bigger than length of run_b
        else:
            merge_high(lst, run_a, run_b, 7)

    def merge_low(lst, a, b, min_gallop):
        """Merges the two runs quasi in-place if a is the smaller run
        - a and b are lists that store data of runs
        - min_gallop: threshold needed to switch to galloping mode
        - galloping mode: uses gallop() to 'skip' elements instead of linear merge"""

        # Make a copy of the run a, the smaller run
        temp_array = make_temp_array(lst, a[0], a[1])
        # The first index of the merging area
        k = a[0]
        # Counter for the temp array of a
        i = 0
        # Counter for b, starts at the beginning
        j = b[0]

        gallop_thresh = min_gallop
        while True:
            a_count = 0  # number of times a win in a row
            b_count = 0  # number of times b win in a row

            # Linear merge mode, taking note of how many times a and b wins in a row.
            # If a_count or b_count > threshold, switch to gallop
            while i <= len(temp_array) - 1 and j <= b[1]:

                # if elem in a is smaller, a wins
                if temp_array[i] <= lst[j]:
                    lst[k] = temp_array[i]
                    k += 1
                    i += 1

                    a_count += 1
                    b_count = 0

                    # If a runs out during linear merge
                    # Copy the rest of b
                    if i > len(temp_array) - 1:
                        while j <= b[1]:
                            lst[k] = lst[j]
                            k += 1
                            j += 1
                        return

                    # threshold reached, switch to gallop
                    if a_count >= gallop_thresh:
                        break

                # if elem in b is smaller, b wins
                else:
                    lst[k] = lst[j]
                    k += 1
                    j += 1

                    a_count = 0
                    b_count += 1

                    # If b runs out during linear merge
                    # copy the rest of a
                    if j > b[1]:
                        while i <= len(temp_array) - 1:
                            lst[k] = temp_array[i]
                            k += 1
                            i += 1
                        return

                    # threshold reached, switch to gallop
                    if b_count >= gallop_thresh:
                        break

            # If one run is winning consistently, switch to galloping mode.
            # i, j, and k are incremented accordingly
            while True:
                # Look for the position of b[j] in a
                # bisect_left() -> a_adv = index in the slice [i: len(temp_array)]
                # so that every elem before temp_array[a_adv] is strictly smaller than lst[j]
                a_adv = gallop(temp_array, lst[j], i, len(temp_array), True)

                # Copy the elements prior to a_adv to the merge area, increment k
                for x in range(i, a_adv):
                    lst[k] = temp_array[x]
                    k += 1

                # Update the a_count to check successfulness of galloping
                a_count = a_adv - i

                # Advance i to a_adv
                i = a_adv

                # If run a runs out
                if i > len(temp_array) - 1:
                    # Copy all of b over, if there is any left
                    while j <= b[1]:
                        lst[k] = lst[j]
                        k += 1
                        j += 1
                    return

                # Copy b[j] over
                lst[k] = lst[j]
                k += 1
                j += 1

                # If b runs out
                if j > b[1]:
                    # Copy all of a over, if there is any left
                    while i < len(temp_array):
                        lst[k] = temp_array[i]
                        k += 1
                        i += 1
                    return

                # ------------------------------------------------------

                # Look for the position of a[i] in b
                # b_adv is analogous to a_adv
                b_adv = gallop(lst, temp_array[i], j, b[1] + 1, True)
                for y in range(j, b_adv):
                    lst[k] = lst[y]
                    k += 1

                # Update the counters and check the conditions
                b_count = b_adv - j
                j = b_adv

                # If b runs out
                if j > b[1]:
                    # copy the rest of a over
                    while i <= len(temp_array) - 1:
                        lst[k] = temp_array[i]
                        k += 1
                        i += 1
                    return

                # copy a[i] over to the merge area
                lst[k] = temp_array[i]
                i += 1
                k += 1

                # If a runs out
                if i > len(temp_array) - 1:
                    # copy the rest of b over
                    while j <= b[1]:
                        lst[k] = lst[j]
                        k += 1
                        j += 1
                    return

                # if galloping proves to be unsuccessful, return to linear
                if a_count < gallop_thresh and b_count < gallop_thresh:
                    break

            # punishment for leaving galloping
            # makes it harder to enter galloping next time
            gallop_thresh += 1

    def merge_high(lst, a, b, min_gallop):
        """Merges the two runs quasi in-place if b is the smaller run
        - Analogous to merge_low, but starts from the end
        - a and b are lists that store data of runs
        - min_gallop: threshold needed to switch to galloping mode
        - galloping mode: uses gallop() to 'skip' elements instead of linear merge"""

        # Make a copy of b, the smaller run
        temp_array = make_temp_array(lst, b[0], b[1])

        # Counter for the merge area, starts at the last index of array b
        k = b[1]
        # Counter for the temp array

        i = len(temp_array) - 1  # Lower bound is 0

        # Counter for a, starts at the end this time
        j = a[1]

        gallop_thresh = min_gallop
        while True:
            a_count = 0  # number of times a win in a row
            b_count = 0  # number of times b win in a row

            # Linear merge, taking note of how many times a and b wins in a row.
            # If a_count or b_count > threshold, switch to gallop
            while i >= 0 and j >= a[0]:
                if temp_array[i] > lst[j]:
                    lst[k] = temp_array[i]
                    k -= 1
                    i -= 1

                    a_count = 0
                    b_count += 1

                    # If b runs out during linear merge
                    if i < 0:
                        while j >= a[0]:
                            lst[k] = lst[j]
                            k -= 1
                            j -= 1
                        return

                    if b_count >= gallop_thresh:
                        break

                else:
                    lst[k] = lst[j]
                    k -= 1
                    j -= 1

                    a_count += 1
                    b_count = 0

                    # If a runs out during linear merge
                    if j < a[0]:
                        while i >= 0:
                            lst[k] = temp_array[i]
                            k -= 1
                            i -= 1
                        return

                    if a_count >= gallop_thresh:
                        break

            # i, j, k are DECREMENTED in this case
            while True:
                # Look for the position of b[i] in a[0, j + 1]
                # ltr = False -> uses bisect_right()
                a_adv = gallop(lst, temp_array[i], a[0], j + 1, False)

                # Copy the elements from a_adv -> j to merge area
                # Go backwards to the index a_adv
                for x in range(j, a_adv - 1, -1):
                    lst[k] = lst[x]
                    k -= 1

                # # Update the a_count to check successfulness of galloping
                a_count = j - a_adv + 1

                # Decrement index j
                j = a_adv - 1

                # If run a runs out:
                if j < a[0]:
                    while i >= 0:
                        lst[k] = temp_array[i]
                        k -= 1
                        i -= 1
                    return

                # Copy the b[i] into the merge area
                lst[k] = temp_array[i]
                k -= 1
                i -= 1

                # If a runs out:
                if i < 0:
                    while j >= a[0]:
                        lst[k] = lst[j]
                        k -= 1
                        j -= 1
                    return

                # -------------------------------------------------

                # Look for the position of A[j] in B:
                b_adv = gallop(temp_array, lst[j], 0, i + 1, False)
                for y in range(i, b_adv - 1, -1):
                    lst[k] = temp_array[y]
                    k -= 1

                b_count = i - b_adv + 1
                i = b_adv - 1

                # If b runs out:
                if i < 0:
                    while j >= a[0]:
                        lst[k] = lst[j]
                        k -= 1
                        j -= 1
                    return

                # Copy the a[j] back to the merge area
                lst[k] = lst[j]
                k -= 1
                j -= 1

                # If a runs out:
                if j < a[0]:
                    while i >= 0:
                        lst[k] = temp_array[i]
                        k -= 1
                        i -= 1
                    return

                # if galloping proves to be unsuccessful, return to linear
                if a_count < gallop_thresh and b_count < gallop_thresh:
                    break

            # punishment for leaving galloping
            gallop_thresh += 1

    def merge_collapse(lst, stack):
        """The last three runs in the stack is A, B, C.
        Maintains invariants so that their lengths: A > B + C, B > C
        Translated to stack positions:
        stack[-3] > stack[-2] + stack[-1]
        stack[-2] > stack[-1]
        Takes a stack that holds many lists of type [s, e, bool, length]"""

        # This loops keeps running until stack has one element
        # or the invariant holds.
        while len(stack) > 1:
            if len(stack) >= 3 and stack[-3][3] <= stack[-2][3] + stack[-1][3]:
                if stack[-3][3] < stack[-1][3]:
                    # merge -3 and -2, merge at -3
                    merge(lst, stack, -3)
                else:
                    # merge -2 and -1, merge at -2
                    merge(lst, stack, -2)
            elif stack[-2][3] <= stack[-1][3]:
                # merge -2 and -1, merge at -2
                merge(lst, stack, -2)
            else:
                break

    def merge_force_collapse(lst, stack):
        """When the invariant holds and there are > 1 run
        in the stack, this function finishes the merging"""
        while len(stack) > 1:
            # Only merges at -2, because when the invariant holds,
            # merging would be balanced
            merge(lst, stack, -2)

    # Starting index
    s = 0

    # Ending index
    e = len(lst) - 1

    # The stack
    stack = []

    # Compute min_run using size of lst
    min_run = merge_compute_minrun(len(lst))

    while s <= e:

        # Find a run, return [start, end, bool, length]
        run = count_run(lst, s)

        # If decreasing, reverse
        if run[2] == False:
            reverse(lst, run[0], run[1])
            # Change bool to True
            run[2] = True

        # If length of the run is less than min_run
        if run[3] < min_run:
            # The number of indices by which we want to extend the run
            # either by the distance to the end of the lst
            # or by the length difference between run and minrun
            extend = min(min_run - run[3], e - run[1])

            # Extend the run using binary insertion sort
            bin_sort(lst, run[0], run[1], extend)

            # Update last index of the run
            run[1] = run[1] + extend

            # Update the run length
            run[3] = run[3] + extend

        # Push the run into the stack
        stack.append(run)

        # Start merging to maintain the invariant
        merge_collapse(lst, stack)

        # Update starting position to find the next run
        # If run[1] == end of the lst, s > e, loop exits
        s = run[1] + 1

    # Some runs might be left in the stack, complete the merging.
    merge_force_collapse(lst, stack)

    return lst


def retrieve_name(var):
    callers_local_vars = inspect.currentframe().f_back.f_locals.items()
    return [var_name for var_name, var_val in callers_local_vars if var_val is var]


def switch(name):
    return {
        "array1": "Random",
        "array2": "Decending sorted",
        "array3": "Ascending sorted",
        "array4": "Partially sorted",
        "array5": "Ksorted",
        "array6": "All equal",
        "array7": "Almost equal",
        "array8": "Hole",
    }.get(name, "")


def saveResultAsPNG(timeResults, name, title):
    times = []
    labels = []
    # Sort dictionary by values
    for key, value in sorted(timeResults.items(), key=lambda x: x[1]):
        times.append(value)
        labels.append(key)

    plt.figure(figsize=(10, 8), dpi=80)  # 800 x 640

    ax = plt.subplot()
    ax.set_xticks(range(len(times)))
    ax.set_xticklabels(labels, rotation=15)

    plt.bar(range(len(times)), times)

    plt.title(f"{title} (n: {ARRAY_LENGTH})")
    plt.ylabel('Times (sec)')

    plt.savefig(name)


toaster = ToastNotifier()
toaster.show_toast("Sorting",
                   "Sorting algorithms are running",
                   icon_path="D:\DEV\Code\Python\img\python.ico",
                   duration=2)


# setrecursionlimit(ARRAY_LENGTH)

if __name__ == "__main__":
    lib = bigO.bigO()
    ARRAY_LENGTH = 10000
    
    # Random
    array1 = lib.genRandomArray(ARRAY_LENGTH)
    # Decending sorted
    array2 = lib.genReversedArray(ARRAY_LENGTH)
    # Ascending sorted
    array3 = lib.genSortedArray(ARRAY_LENGTH)
    # Partially sorted
    array4 = lib.genPartialArray(ARRAY_LENGTH)
    # Ksorted
    array5 = lib.genKsortedArray(ARRAY_LENGTH, ARRAY_LENGTH.bit_length())
    # Equal
    array6 = lib.genEqualArray(ARRAY_LENGTH)
    # Almost Equal
    array7 = lib.genAlmostEqualArray(ARRAY_LENGTH)
    # Hole
    array8 = lib.genHoleArray(ARRAY_LENGTH)
    
    run = {
        sorted: 0,
        countSort: 0,
        introSort: 0,
        timSort: 0,
        quickSort2: 0,
        mergeSort: 0,
        heapSort: 0,
        heapSort2: 0,
        smoothSort: 0,
        pancakeSort: 0,
        insertSort: 0,
        insertSort2: 0,
        binaryInsertSort: 0,
        bubbleSort: 0,
        goSort: 0
    }
    
    test = [array1, array2, array3, array4, array5, array6, array7, array8]
    for index in range(len(test)):
        for function in run.keys():
            testArray = test[index].copy()  # Shallow Copy
            runAlgorithm3(algorithm=function, array=testArray, timeResults=run)

        # name = switch(retrieve_name(test[index]))
        name = switch(retrieve_name(test[index])[0])
        saveResultAsPNG(run, f"array{index + 1}.png", name)

    # runAlgorithm(algorithm="bogoSort", array=testArray, timeResults=times)

    toaster.show_toast(
        "Sorting", "Measurements are made", icon_path=None, duration=5, threaded=False
    )

requirements.txt

win10toast == 0.9
matplotlib == 3.3.1
big-O-calculator == 0.0.9.8.2