Merge sort algorithm.

Merge sort use case.


Merge Sort is considered as one of the most accepted and used sorting algorithms which is based on the concept of Divide and Conquer Algorithm (Algorithmic Paradigm).

The list is divided into two equal halves and then they are combined in a sorted manner. It is a recursive method that continuously splits the list in 2 halves until it cannot be further divided, i e if the list becomes empty or has only one element left, the recursion will stop.

Merge sort algorithm.



When both the halves are sorted, it's time for the merge operation, which is responsible of taking two smaller sorted lists and combining them to eventually make a larger one.

Merge Sort is considered slower comparative to the other sort algorithms for smaller tasks.


Merge Sort Python code:



def merge_Sort(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
        merge_Sort(L)
        merge_Sort(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()


if __name__ == '__main__':
    array = [-10, 35, 0, 13, -7]

    merge_Sort(array)

    print("Sorted elements in ascending order: ")
    printList(array)

OUT: Sorted elements in ascending order:
-10 -7 0 13 35





See also related topics: