"""
Merge Sort
    We have 2 unsorted arrays, we've to sort them and merge them in a way that merged array is also a sorted array
    Traditional Method
        Compare first element of each array
            Insert the smallest element into sorted array
        Compare greater element from previous array and 2nd element from 2nd array
            Insert the smallest element into sorted array
        Repeat until array is sorted


                    9 - 2 - 1 - 7 - 5 - 3 - 4 - 6
                  9 - 2 - 1 - 7       5 - 3 - 4 - 6
               9 - 2    1 - 7           5 - 3    4 - 6
             2 - 9    1 - 7               3 - 5    4 - 6
           1 - 2  -  7 - 9                 3 - 4  -  5 - 6
               1 - 2 - 7 - 9              3 - 4 - 5 - 6
                      1 - 2 - 3 - 4 - 5 - 6 - 7 - 9


Time Complexity: O(n log n)


"""

def Merge2SortedList(arr1, arr2):
    """Input: 2 sorted lists"""
    sortedList = []  # created an empty sorted list
    len_arr1 = len(arr1)  # length of array1
    len_arr2 = len(arr2)  # length of array2
    i = j = 0  # pointers initialised
    # iterate through both lists until end of any of them is reached
    while i < len_arr1 and j < len_arr2:
        if arr1[i] <= arr2[j]:  # compare elements between both the lists
            sortedList.append(arr1[i])  # append to sorted list
            i+=1  # i pointer is increased by 1 and j pointer is static
        else:
            sortedList.append(arr2[j])
            j+=1
    while i < len_arr1:
        sortedList.append(arr1[i])
        i+=1
    while j < len_arr2:
        sortedList.append(arr2[j])
        j += 1
    return sortedList  # sorted list returned


def MergeSort(arr):
    # if list is empty or contains 1 element only: return list
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2  # get middle index of array to divide it into 2 parts: left and right
    left = arr[:mid]  # dividing list into 2 parts: left and right
    right = arr[mid:]  # dividing list into 2 parts: left and right

    left = MergeSort(left)  # recursively call MergeSort function to sort left array
    right = MergeSort(right)  # recursively call MergeSort function to sort right array
    # MergeSort(left)  # recursively call MergeSort function to sort left array
    # MergeSort(right)  # recursively call MergeSort function to sort right array

    return Merge2SortedList(left, right)  # Merge Sort both sorted array
    # Merge2SortedList(left, right)  # Merge Sort both sorted array


if __name__ == '__main__':

    """arr1 = [2, 4, 6, 8]
    arr2 = [3, 6, 9, 12]
    print(Merge2SortedList(arr1, arr2))"""
    arr = [10, 3, 15, 7, 8, 23, 98, 29]
    print(MergeSort(arr))

    # test cases

    tests = [
        [20, 13, 5, 37, 8, 32, 98, 29],  # unsorted array
        [],  # empty array
        [5],  # array with single element
        [10, 8, 6, 4, 2],  # reverse array
        [1, 2, 3, 4, 5]  # sorted array
    ]
    for elements in tests:
        print(MergeSort(elements))