Merge Sort in 2 Minutes | All You Need to Know #mergesort #dsa #daa #shorts #coding #recap

Ajouté : 2026-05-17

[00:00:01]Hello everyone.

[00:00:02]Let's just have a quick recap about merge sort and let me tell you what are the points you need to remember whenever you hear the word merge sort.

[00:00:09]First of all, what is merge sort?

[00:00:11]It is an algorithm that is used to sort the elements in either ascending or in descending manner.

[00:00:17]This particular merge sort works in data structures like array as well as linked list.

[00:00:22]And this merge sort follows the divide and conquer paradigm.

[00:00:26]How does it work basically? There are two functions. One is the merge sort function itself, another is the merge function. How does this merge sort function work?

[00:00:35]It finds the middle element of the array and then it breaks it down into two parts, the left part and the right part, and then it keeps on calling itself recursively on the left sub part as well as on the right sub part. And it breaks the array until and unless it cannot break anymore. That is, it reaches the base condition, only one element is left.

[00:00:54]At that point, it starts merging back.

[00:00:57]And it calls a merge function. How does the merge function work? It basically suppose there are two arrays, two sorted array. There are two pointers. One is at the first array's first index, another is the second array's first index. So, it will be comparing those two elements.

[00:01:12]Whoever is smaller, that will be going to the final array.

[00:01:16]And whoever is going to the final array, that particular pointer will be moved to one step ahead. And this process will keep on repeating until and unless we're getting the final desired outcome.

[00:01:26]This merge sort is also known as stable sorting because whatever be the input, if there are two similar elements, say there are two 23s, so in that case, they will be preserving their order whenever the output is generated.

[00:01:40]Whichever 23 has came first in the input, that will be there in the first in the output as well.

[00:01:45]This merge sort, because it is recursive, so it has a recurrence relation, that is, T of N, that is the time taken for N elements equals to 2 T N by 2 plus N.

[00:01:55]What is that two in front of the T? That is it is dividing into two sub parts and n by two is nothing but the size of each sub parts at every time.

[00:02:05]And what is that plus n? That plus n is the time taken for merging all these things back.

[00:02:10]And what is the worst case, best case, and average case time complexity of merge sort? Everything is order of n log n.

[00:02:16]And what is the time and space trade off? That is this particular merge sort works really, really fast in order of n log n time, but it takes extra array.

[00:02:26]That is while merging back we need the help of an extra array. So, the space complexity is order of n.

[00:02:32]So, that is all about merge sort and whatever I have talked about in this video, all these videos are detailed available in my data playlist. So, you can check out. I am pinning them down in the pinned comment. Thank you for watching.