Summer training at Goeduhub Technologies-Jaipur
Register for Free Certified Workshop on AI & Machine Learning:: 23-02-2020 ||  Career options for aspiring CS/ITECEEE or EIC or EEE Engineers
0 like 0 dislike
12 views
in Tutorial & Interview questions by (6.7k points)

1 Answer

0 like 0 dislike
by (6.7k points)
 
Best answer

Merge Sort is a Divide and Conqure algorithm. It divides input array in two halves, calls itself for the two halves and then merges the two sorted halves. The merge() function is used for merging two halves. 

Auxiliary Space  :   O(n)

Time complexity :  θ(nlog(n))

merge-sort-python-program

Python program for implementation of Merge Sort:

def mergeSort(arr):

    if len(arr) >1:

        mid = len(arr)//2 

        L = arr[:mid]

        R = arr[mid:]

         mergeSort(L)

        mergeSort(R)

         i = j = k = 0

         # 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

        while i < len(L):

            arr[k] = L[i]

            i+=1

            k+=1

         

        while j < len(R):

            arr[k] = R[j]

            j+=1

            k+=1        

a=[12,11,8,5,3,20]

mergeSort(a)

print(a)

 

 Go to your Branch CSE or IT | ECE | EE, EIC or EEEMECE
 Know About Popular Colleges/Universities  List of IITsList of NITs | RTU-KOTA | Manipal University-Jaipur | JECRC University | Amity University Jaipur | BIT Mesra-Jaipur | MODY UNIVERSITY | LNMIIT-Jaipur | JK Lakshmipat | Banasthali Vidyapith | POORNIMA University
 Exams:   List of Exams After Graduation | List of Engineering Entrance Examinations (UG/PG) | JEE Main | JEE Advanced | GATE | IES | ISROList of PSUs
Placements:  List of companies | Logical Reasoning Questions | Quantitative Aptitude Questions | General English Questions | Technical-MCQ and Interview Questions
 Download Previous Year Papers For:  GATE | IES | RAJASTHAN TECHNICAL UNIVERSITY (RTU-Kota)RPSC Technical Exams | ISRO
 Online Free Training:  Artificial Intelligence(AI) Machine Learning(ML)Python Programming | Internet of Things-IoT | OpenCV (Open Source Computer Vision Library) | LINUX | Big Data : Hadoop | 
 Goeduhub
About Us | Contact Us   Social::   |  | 
...