import random
import time
from typing import Any


##################################################################################################
# 1. INSERTION SORT


# Insertion sort is:
# 1. stable
# 2. inplace
# 3. fast for small arrays(or almost sorted arrays)
# 4. O(n^2) time perfomance & O(1) space complexity
def insertion_sort(arr: list):
    """
    1. Iterate from arr[1] to arr[n]
    2. Compare the current_element to the previous_one
    3. If the current_element < previous_one, compare it to ALL the elements before
    4. Move the greater elements one position up to make space for the swapped element
    """
    for i in range(1, len(arr)):
        nums_b4 = i
        c_value = arr[i]
        while nums_b4 > 0:
            if c_value < arr[nums_b4 - 1]:
                arr[nums_b4], arr[nums_b4 - 1] = arr[nums_b4 - 1], arr[nums_b4]
            nums_b4 = nums_b4 - 1


arr = [1, 6, 2, 96, 346, 8, 5]
insertion_sort(arr)

if arr != sorted(arr):
    raise Exception(
        """The `insertion_sort` algo didnt work.
        \ngot = {}. \nexpected = {}.""".format(
            arr, sorted(arr)
        )
    )


# 2. SORT CUSTOM OBJECTS
class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __repr__(self):
        return f"Point({self.x})"


def compare_func(a: Any, b: Any) -> bool:
    # We sort by the x coordinate, ascending
    return a.x < b.x


def custom_insertion_sort(arr: list, compare_func):
    for i in range(1, len(arr)):
        nums_b4 = i
        c_value = arr[i]
        while nums_b4 > 0:
            if compare_func(c_value, arr[nums_b4 - 1]):
                arr[nums_b4], arr[nums_b4 - 1] = arr[nums_b4 - 1], arr[nums_b4]
            nums_b4 = nums_b4 - 1


ct_array = [Point(4, 4), Point(1, 2), Point(10, 0), Point(3, 1)]
custom_insertion_sort(ct_array, compare_func)
if ct_array != sorted(ct_array, key=lambda a: a.x):
    raise Exception(
        """The `insertion_sort` algo didnt work.
        \ngot = {}. \nexpected = {}.""".format(
            ct_array, sorted(ct_array, key=lambda a: a.x)
        )
    )
##################################################################################################

# 3. MERGE SORT


# Merge sort is:
# 1. stable
# 2. NOT in-place
# 3. Uses Divide and Conquer
# 4. O(n log n) performance & O(n) space complexity
# 5. Good for large arrays, slower than insertion sort for small arrays.
def merge_sort(arr: list):
    if len(arr) > 1:
        middle = len(arr) // 2
        left_arr = arr[:middle]
        right_arr = arr[middle:]

        merge_sort(left_arr)
        merge_sort(right_arr)
        merge(arr, left_arr, right_arr)


def merge(arr: list, left: list, right: list):
    # Two iterators for traversing the two halves
    i = 0
    j = 0
    # Iterator for the main list
    k = 0

    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            arr[k] = left[i]
            i += 1
        else:
            arr[k] = right[j]
            j += 1
        k += 1

    # For all the remaining values
    while i < len(left):
        arr[k] = left[i]
        i += 1
        k += 1
    while j < len(right):
        arr[k] = right[j]
        j += 1
        k += 1


arr = [1, 6, 2, 96, 346, 8, 5, 90]
merge_sort(arr)
if arr != sorted(arr):
    raise Exception(
        """The `merge_sort` algo didnt work.
        \ngot = {}. \nexpected = {}.""".format(
            arr, sorted(arr)
        )
    )


#### comparison of insertion_sort & merge_sort ####

arr = []
for i in range(45):
    arr.append(random.randint(0, 99_999_999))
start_insertion_sort = time.monotonic()
insertion_sort(arr)
end_insertion_sort = time.monotonic()
arr = []
if arr != sorted(arr):
    raise Exception(
        """The `insertion_sort` algo didnt work.
        \ngot = {}. \nexpected = {}.""".format(
            arr[:8], sorted(arr)[:8]
        )
    )
insertion_sort_duration = end_insertion_sort - start_insertion_sort
print(
    "`insertion_sort` of an array of length:{} took {}secs".format(
        len(arr), insertion_sort_duration
    )
)


arr = []
for i in range(45):
    arr.append(random.randint(0, 99_999_999))
start_merge_sort = time.monotonic()
merge_sort(arr)
end_merge_sort = time.monotonic()
arr = []
if arr != sorted(arr):
    raise Exception(
        """The `merge_sort` algo didnt work.
        \ngot = {}. \nexpected = {}.""".format(
            arr[:8], sorted(arr)[:8]
        )
    )
merge_sort_duration = end_merge_sort - start_merge_sort
print("`merge_sort` of an array of length:{} took {}secs".format(len(arr), merge_sort_duration))


# insertion_sort seems to perform better than merge_sort when len(arr)<=40