Merge Sort Algorithm [with Animated Example]

In this video, I will show you how Merge Sort works - and how you can determine Merge Sort's time and space complexity without complicated math.
I explain the Mergesort algorithm with an example, using animations and visualizations. I show you visually how to determine the time complexity and what "quasilinear time" - O(n log n) - means for algorithms.
On the HappyCoders.eu website, you can learn how to implement Mergesort in Java:
www.happycoders.eu/algorithms...
All parts of this video series:
* Insertion Sort: • Insertion Sort Algorit...
* Selection Sort: • Selection Sort Algorit...
* Bubble Sort: • Bubble Sort Algorithm ...
* Quicksort: • Quicksort Algorithm [w...
* Merge Sort: • Merge Sort Algorithm [...
You can find an overview of the most important sorting algorithms here:
www.happycoders.eu/algorithms...
Download my FREE "Big O Cheat Sheet" here:
www.happycoders.eu/big-o-chea...
Happy Coding!
(Author: Sven Woltmann)

[@hasni7047]

The way you explained the Run Time Complexity is Excellent. Thanks a lot.

[@drfitingaway7372]

Well explained! Frequetly asked question!

[@romanlunin386]

A real nice explanation, thanks!

[@martins.7930]

Thank you, that was really well explained!

[@ITKalashKumar]

tq for the video sir.

[@yusufmirkar6508]

for n=8, we have 15 divisions, why we did not calculate the last row ?

[@HappyCoders]

In the last row, there are only single elements that need no further splitting up.

[@yusufmirkar6508]

@@HappyCoders ok just clear my doubts, we check how many times recursion call is made, right ? if not, what is time complexity exactly then ?

[@HappyCoders]

Yes: in the division phase, we count how many times we calculate the middle and call the recursion. That number grows linearly with the number of elements, so O(n).
But the time complexity of the merge phase is O(n log n), which “trumps” the O(n) of the division phase, so the total time complexity is also O(n log n).

[@yusufmirkar6508]

@@HappyCoders Got some idea from your reply. So if I have to calculate time complexity, what is the general rule, is it like no of recursion call * some operation.or how ? in short I want to know by which formula n + nlogn came & then we use nlogn (which i understood) but how n+nlogn came that I did not understood

[@HappyCoders]

@@yusufmirkar6508 Maybe have a look at this article, here I explain the fundamentals of time complexity: www.happycoders.eu/algorithms/big-o-notation-time-complexity/