Merge Sort Pseudocode | Merge Sort with example

👉Links for DAA Notes:

🧑‍🎓Contributed by: Junaid Gazi

🧑‍🎓Contributed by: Mannu Garg

Merge sort is one of the most efficient sorting techniques and it’s based on the “divide and conquer” paradigm.
In merge sort, the problem is divided into two subproblems in every iteration.
Hence efficiency is increased drastically.
Declare left and right var which will mark the extreme indices of the array
Left will be assigned to 0 and right will be assigned to n-1
Find mid = (left +right)/2
Call merge Sort on (left, mid) and (mid+1,rear)
Above will continue till left is less than right
Then we will call merge on the 2 subproblems.
Time Complexity of Merge sort
In the worst case, in every iteration, we are dividing the problem into further 2 subproblems. Hence this will perform log n operations and this has to be done for n iteration resulting in n log n operations total.
In the best case that is sorted array, we can do some modification by using a flag to check whether the lament is already sorted or not
Best Time Complexity: O(nlogn)
Average Time Complexity: O(nlogn)
Worst Time Complexity: O(nlogn)

►Design and Analysis of algorithms (DAA) (Complete Playlist):

Other subject-wise playlist Links:
--------------------------------------------------------------------------------------------------------------------------------------
► Operating System :
►Database Management System:
► Theory of Computation
►Artificial Intelligence:
►Computer Networks (Complete Playlist):
►Computer Architecture (Complete Playlist):
►Structured Query Language (SQL):
►Discrete Mathematics:
►Compiler Design:
►Number System:
►Cloud Computing & BIG Data:
►Software Engineering:
►Data Structure:
►Graph Theory:
►Programming in C:
►Digital Logic:

---------------------------------------------------------------------------------------------------------------------------------------
Our social media Links:
--------------------------------------------------------------------------------------------------------------------------------------
►For Any Query, Suggestion or notes contribution:

[bhumikasingh]

not just a teacher ...you are a saviour!!!

[GauravKumar-xvrp]

I completed my OS and DBMS from gate smashers, and even revise the playlist whenever required before interview.
Thank You Sir for covering all the concepts.

[shubhamchauhan]

In psuedo code, line 14th there should be L[i] in place of L[j]

[facts_shorts]

at 7:21, In line No. 14 there will be L[ i ] instead of L[ j ];

[niazmir]

In line No. 14 there will be L[I] instead of L[j]

[HellshotGaming]

In line 14th, in place of R[j] there should be L[i]

[aminjan]

AJ Dil SE Dua nikli AP k Liye. Hamesha khush awr sakoon se Rahi. Amen

[haniakhan]

Red shirt se green shirt tak ka safar hai bs yaro

[NavjotSingh-nvhy]

Thanks sir for your help in our engineering thanku sir love form punjab😊

[jagritrattan]

Sir I understood the concept that you explained, there is typing mistake in Merge code in line 14 in which there is a comparison 1st value of L with R. L[i]<=R[j] then A[k]=L[i] but instead of L[i], L[j] is written

[sheetalsisodia]

Hello Sir, i really loved the way you explain different-different concepts of various subjects, please keep doing this sir, lots of thanks and appreciation from my side, i had never ever subscribed any channel till now, this is first time i subscribed any channel :)

[huriarauf]

Thank you much lov from Pakistan 🇵🇰🇵🇰🇵🇰🇵🇰🇵🇰

[Nehajoshi]

I think L(j) ki place par hum l(i) dalenge a(k) main

[pallavsadhukhan]

Sir last part ka 14 no line pe L[j] ke place sayed L[i] hoga.

[NavinKumar-lcfn]

Tractable and Intractable Problems
Computability of Algorithms, Computability classes – P, NP, NP-complete and NP-hard.
Cook’s theorem, Standard NP-complete problems and Reduction techniques.

[fawadziakhan]

Excellent explanation of this rather confusing pseudo code in the Algorithms textbook. Btw, is there any way you can also explain how to do a three way merge sort in pseudo code form?

[steverogers]

Great content sir you made it very easy .

[NurgusSajad]

why we use floor fucntion in merge sort?