from datetime import datetime

my_array = [9, 9, 9, 7, 1, 0, 6, 7, 1, 0, 8, 9, 6, 4, 7]
print(my_array)

print('\n')
print("***СОРТИРОВКА СЛИЯНИЕМ***")
start_time = datetime.now()


def merge(left_list, right_list):
    sorted_list = []
    left_list_index = right_list_index = 0
    left_list_length, right_list_length = len(left_list), len(right_list)
    for _ in range(left_list_length + right_list_length):
        if left_list_index < left_list_length and right_list_index < right_list_length:
            if left_list[left_list_index] <= right_list[right_list_index]:
                sorted_list.append(left_list[left_list_index])
                left_list_index += 1
            else:
                sorted_list.append(right_list[right_list_index])
                right_list_index += 1
        elif left_list_index == left_list_length:
            sorted_list.append(right_list[right_list_index])
            right_list_index += 1
        elif right_list_index == right_list_length:
            sorted_list.append(left_list[left_list_index])
            left_list_index += 1
    return sorted_list


def merge_sort(nums):
    if len(nums) <= 1:
        return nums
    mid = len(nums) // 2
    left_list = merge_sort(nums[:mid])
    right_list = merge_sort(nums[mid:])
    return merge(left_list, right_list)


my_array_merge_sort = merge_sort(my_array)
print(my_array_merge_sort)

end_time = datetime.now()
print('Duration of Merge Sort: {}'.format(end_time - start_time))

print('\n')
print("***СОРТИРОВКА КУЧЕЙ***")
start_time = datetime.now()


def heapify(nums, heap_size, root_index):
    largest = root_index
    left_child = (2 * root_index) + 1
    right_child = (2 * root_index) + 2
    if left_child < heap_size and nums[left_child] > nums[largest]:
        largest = left_child
    if right_child < heap_size and nums[right_child] > nums[largest]:
        largest = right_child
    if largest != root_index:
        nums[root_index], nums[largest] = nums[largest], nums[root_index]
        heapify(nums, heap_size, largest)


def heap_sort(nums):
    n = len(nums)
    for i in range(n, -1, -1):
        heapify(nums, n, i)
    for i in range(n - 1, 0, -1):
        nums[i], nums[0] = nums[0], nums[i]
        heapify(nums, i, 0)


my_array_heap_sort = my_array
heap_sort(my_array_heap_sort)
print(my_array_heap_sort)

end_time = datetime.now()
print('Duration of Heap Sort: {}'.format(end_time - start_time))

print('\n')
print("***БЫСТРАЯ СОРТИРОВКА***")
start_time = datetime.now()


def partition(nums, low, high):
    pivot = nums[(low + high) // 2]
    i = low - 1
    j = high + 1
    while True:
        i += 1
        while nums[i] < pivot:
            i += 1
        j -= 1
        while nums[j] > pivot:
            j -= 1
        if i >= j:
            return j
        nums[i], nums[j] = nums[j], nums[i]


def quick_sort(nums):
    def _quick_sort(items, low, high):
        if low < high:
            split_index = partition(items, low, high)
            _quick_sort(items, low, split_index)
            _quick_sort(items, split_index + 1, high)
    _quick_sort(nums, 0, len(nums) - 1)


my_array_quick_sort = my_array
quick_sort(my_array_quick_sort)
print(my_array_quick_sort)

end_time = datetime.now()
print('Duration of Quick Sort: {}'.format(end_time - start_time))