Free Online Tutorials ==>> Machine Learning || Python Programming || DBMS || OOPs using C++ || DSA || Java Programming || Linux/Unix || C Programming
Go to your University || Python Lab || DSA Lab || AI & Machine Learning Lab || Linux Lab || OOPs Lab || DBMS Lab || JAVA Lab ||| Free Online Tutorials ||| 
companies for Campus Placement || Logical Reasoning || Quantitative Aptitude || General English || Technical-MCQ and Interview Questions || HR Interview Questions
0 like 0 dislike
19 views

1 Answer

0 like 0 dislike
by Goeduhub's Expert (7.8k 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)

 

Related questions

0 like 0 dislike
0 answers 16 views
0 like 0 dislike
1 answer 35 views
0 like 0 dislike
1 answer 122 views
0 like 0 dislike
1 answer 38 views
  Realize your learning potential with courses starting at ₹ 420
 Placements:   List of companies | Logical Reasoning Questions | Quantitative Aptitude Questions | General English Questions | Technical-MCQ and Interview Questions
 Online Free Training:  MACHINE LEARNINGPython Programming | Database Management System(DBMS) | Object Oriented Programming(OOPs) using C++ | Data Structures and Algorithms(DSA) | Java Programming | Linux/Unix | C Programming
Exams: List of Exams After Graduation | List of Engineering Entrance Examinations (UG/PG) | JEE Main | JEE Advanced | GATE | IES | ISROList of PSUs
 Download Previous Year Papers For:  GATE | IES | RAJASTHAN TECHNICAL UNIVERSITY (RTU-Kota)RPSC Technical Exams | ISRO
 Goeduhub
About Us | Contact Us   Social::   |  | 
...