Merge Sorting

    0

    0

    Mahendra Kumar

    arraysDSAlogic•••

    Merge Sort is one of the most popular sorting algorithms that is based on the principle of the Divide and Conquer Algorithms.

    A divide and conquer algorithm is a strategy for solving a large problem by

    1. breaking the problem into smaller sub-problems
    2. solving the sub-problems, and
    3. Combine them to get the desired output.
    def mergeSort(array):
        if len(array) > 1:
            #  r is the point where the array is divided into two subarrays
            r = len(array)//2
            L = array[:r]
            M = array[r:]
            # Sort the two halves
            mergeSort(L)
            mergeSort(M)
            i = j = k = 0
            # Until we reach either end of either L or M, pick larger among
            # elements L and M and place them in the correct position at A[p..r]
            while i < len(L) and j < len(M):
                if L[i] < M[j]:
                    array[k] = L[i]
                    i += 1
                else:
                    array[k] = M[j]
                    j += 1
                k += 1
            # When we run out of elements in either L or M,
            # pick up the remaining elements and put in A[p..r]
            while i < len(L):
                array[k] = L[i]
                i += 1
                k += 1
            while j < len(M):
                array[k] = M[j]
                j += 1
                k += 1
    # Print the array
    def printList(array):
        for i in range(len(array)):
            print(array[i], end=" ")
        print()
    # Driver program
    if __name__ == '__main__':
        array = [6, 5, 12, 10, 9, 1]
        mergeSort(array)
        print("Sorted array is: ")
        printList(array)
    
    Codiga Logo
    Codiga Hub
    • Rulesets
    • Explore
    • Cookbooks
    • Playground
    soc-2 icon

    We are SOC-2 Compliance Certified

    G2 high performer medal

    Codiga – All rights reserved 2022.