Why Is Merge Sort O(n * log(n))? The Really Really Long Answer.

📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions

Question: Analyze the total work that Merge Sort performs as an exact function of n, the length of the input list.

++++++++++++++++++++++++++++++++++++++++++++++++++

[BackToBackSWE]

Table of Contents (If you watch this all, you will know why Merge Sort is upper bounded by O(n * log(n)))

What This Video Will Cover 0:00 - 0:40
The Fundamental Subroutines 0:40 - 1:32
The Split Subroutine 1:32 - 8:35
The Split Subroutine In Code 8:35 - 11:05
[ Old Clip ] Merge Sort Execution Trace 11:05 - 14:38
The Merge Subroutine 14:38 - 16:54
The Recurrence Relation 16:54 - 21:45
Investigation: What Work Is Done Per Level? 21:45 - 27:10
Getting Exact: Solving For Total Work Across All Levels 27:10 - 30:50
My Whole Life Has Been A Lie 30:50 - 34:51
Checking Our Work 34:51 - 35:48
Wrap Up 35:48 - 36:30

The code for Merge Sort is in the description, fully commented for understanding.

[ful]

The patience you had to go through every literal step, god damn, much appreciated (once again) man.

[Ghareonn]

Bro, you should be the one teaching me algorithms instead of my college professor, good job!

[tomevans]

In my 4 years of doing a Computer Science degree I never had a lecturer explain it this well

[paukatable]

How COME a person can be this talented at teaching? Thank you a million times!

[Rhunyc]

Hey man, just wanted to add a +1 to the supportive comments. I absolutely love how you do not jump over steps assuming people know what's happening. I have a brain that needs to know why every step is included even if some might find it common sense, so this is wonderful for me. I subscribed to you because I think you deserve it. :) Have a wonderful day!

[cristian-razvanpopa]

For those getting stuck at [29:09], there is a 2^i before the parenthesis, but it might not be visible due to board reflections. Thank you for the video as it helped a lot to understand how its complexity is calculated for the first time.

[anthonylee]

Coming from a non-computer science major, real understanding sorting part was always a real pain. (Even with my experience in working as a sw developer).
Just after watching this video for about 5 mins, lightening struck my head.


I've paid more than a few hundred bucks on algorithm + data structure courses, and was never satisfied once.
Your explanation, though it is free, is by far the best, and the only one I was completely satisfied with.


No, it's not just satisfaction, but the best I have ever encountered in my life.
Thank you once again. Truly appreciate your great work.

[Egrodo]

Also found your videos through Leetcode. As someone without a traditional CS background, you have a talent for explaining things in a very clear way. I imagine making these videos must be exhausting, but I do hope you continue. Even if that means one per month :)

[dragoslavmilutinovic]

You are literally only youtuber who gives deep intuition behind this concept, you are giving us feeling like we could invent this by own, much

[starbloods]

literally the best explanation i've ever gotten. i finally get it. i go to a top university but i regret wasting my money when your videos teach me better than my professors

[adrijasamanta]

You have just converted a process of time complexity of O(n ^ to O(log n) in this video with your awesome teaching talent. Really like the way you teach with immense patience and dedication.

[charlieminaya]

The. Best. Explanation. Ever. I have months confused about what it actually meant for it to be nlogn, and it all makes so so much sense now. Thank you a million times. Your videos are THE best. Much appreciated.

[heathledger]

this is the stuff i was trying to find about mergesort, not just the how, but also the why,
everyone else seems to think teaching splitting and merging functions is enough, but until u realize how the process is unfolding practically u never truely "realize" the essense of mergesort.
The thing with recursive algorithms is that they seem very easy and obvious, until u start thinking how the computer actually handles all the states, calls, order of calls, variables etc,
thats probably why everyone tries to talk about recursion on a superficial level.
This video is so great btw .Very in-depth.

[thestudycoven]

^ THIS is how to teach

The way most professors teach is as if they are giving a refresher of something the students have already learned rigorously. They should watch this video and take notes on how to teach.

[hegyilevente]

You are a legend in teaching. Pure and simple explanation with a very patient attitude. It's clear that you don't do the videos to be done, you really want to transfer your knowledge, and you do it the best. I'm happy that i find you. Keep up the good work brother!

[domyi]

I found this channel through your comment in LeetCode, and I'm so glad I was able to find your channel before my tech interview. THANK YOU SO MUCH. KEEP IT GOING

[hrithikjaysingpure]

This is the best explanation of the merge sort on youtube.

[karthikrockrr]

This material is gold and it gives you an order of solving leetcode problems to understand merge sort in dept. Kudos to the creator !

[dawn_connor]

i'm graduated from uni, but my data structures and algorithms professor sucked. this section of CS has been the bane of my existence for a long time now, and i've really appreciated this video. thanks so much. i needed a long explanation like this.