Merge Sort

Merge Sort is a Divide and Conquer algorithm is used to if we have two differrent array. we peak a one one element in both array and place in new array in its correct Position. This Process repet again and again untill our array come in Sorted Form Assending or Dessending Order.

Merge Sort Algorithm Implementation

                    

                        def mergeSort(arr):
                        if len(arr) > 1:
                
                            # todo find mid point of array
                            mid = len(arr) // 2
                
                            # todo Dividing the array elements
                            L = arr[:mid]
                
                            # todo right part
                            R = arr[mid:]
                
                            # todo Sorting the first half
                            mergeSort(L)
                
                            # todo Sorting the second half
                            mergeSort(R)
                
                            i = j = k = 0
                
                            # todo Copy data to temp arrays L[] and R[]
                            while i < len(L) and j < len(R):
                                if L[i] < R[j]:
                                    arr[k] = L[i]
                                    i += 1
                                else:
                                    arr[k] = R[j]
                                    j += 1
                                k += 1
                
                            # todo Checking if any element was left
                            while i < len(L):
                                arr[k] = L[i]
                                i += 1
                                k += 1
                
                            while j < len(R):
                                arr[k] = R[j]
                                j += 1
                                k += 1
                
                    # todo given array
                    arr = [12, 11, 13, 5, 6, 7]
                    print(f"Unsorted Array: {arr}")
                    mergeSort(arr)
                    t = []
                    for i in arr:
                        t.append(i)
                    print(f"Sorted Array: {arr}")
                
                

Merge Short Algorithm Analysis

                    Best Case: O(nlogn)
                    Average Case: O(nlogn)
                    Worst Case: O(nlogn)
                    Space Complecity: O(n)
                    Merge Short Algorithm are External Shorting Algorithm
                    Merge Short Algorithm are Recursive Shorting Algorithm
                    Stability: Yes Merge Short Algorithm Are Stable Algorithm
                    Adpative: Yes Merge Short Algorithm Are Adpative Algorithm
                    Merge Short Algorithm are Slower Algorithm then Other