def MergeSortAlgorithm(arr: list) -> list:
    """
        [ name ] => merge sort
        [ type ] => sorting algorithms
        [ time complexity ] => O(n log n)
        [ space complexity ] => O(n)
        [ params ] => ( 
            arr {list} list to sort
        )
    """
    n = len(arr)
    if n > 1:
        #getting the middle of the giving array 
        mid = n // 2
        # left half 
        leftHalf  =  arr[:mid]
        # right half
        rightHalf =  arr[mid:]
        # sort left half
        MergeSortAlgorithm(leftHalf)
        # sort right half
        MergeSortAlgorithm(rightHalf)

        i = k = j = 0

        while i < len(leftHalf) and j < len(rightHalf):
            if leftHalf[i] > rightHalf[j]:
                arr[k] = rightHalf[j]
                j+=1
            else:
                arr[k] = leftHalf[i]
                i+=1
            k+=1
        # inserting to the sortedArray the rest of the leftHalf
        while i < len(leftHalf):
            arr[k] = leftHalf[i]
            k += 1
            i+=1
        # inserting to the sortedArray the rest of the rightHalf
        while j < len(rightHalf):
            arr[k] = rightHalf[j]
            k+=1
            j+=1