Merge sort algorithm

Definition of the merge sort algorithm

merge sort is an efficient algorithm, and one of Divide and Conquer algorithms that splits the giving array into two halves, and then merge them in a sorted manner.

Time complexity of merge sort

best-case	average case	worst-case
O(n log n)	O(n log n)	O(n log n)

Space complexity

The space complexity of merge sort is O(n)

Advantages of using merge sort algorithm

Fast for large arrays unlike selection, insertion, and bubble sort it doesn't go through the whole array many times.

Disadvantages of using merge sort algorithm

extra space to store subarrays

slow for small arrays

the algorithm does the whole process even the array is already sorted

Implementation of merge sort using python

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