Merge Sort vs Quick Sort
ฝัง
- เผยแพร่เมื่อ 15 ม.ค. 2014
- A demonstration of merge sort and a two round competition between merge sort and quick sort.
See more details here: www.udiprod.com/ms-vs-qs/
Previous match: • Visualization of Quick...
Next match: • Heaps and Heap Sort - วิทยาศาสตร์และเทคโนโลยี
"hey dude what sports do u watch"
me: *_sweats nervously_*
thx my folks for the correction
me: Sorting algorithms!
"what"
It's been 1 month since I replied but I never noticed the misspelling of 'nerviously'. It's supposed to be 'nervously'. How did I not notic that?
said who ?
lets play cricket
@Commenter in a Box r/wooosh time!
“Instead of relying on miracles...”
Bogo sort: 😥
XD
its rare
yes that is true
MiracleSort: 😥
@@astro_cat030 you just don't believe enough
I skipped class, and now I'm cheering on cute little robots running sorting algorithms. What the hell is wrong with my life?
Gretgor LOL
Everything basically.
I know that.
@@GretgorPooper How wrong is your life now? Doing any better?
are you at least a compsci student?
@@daydodog electrical engineering do this aswell
Can we get bogosort?
There's definitely a popular demand for this algorithm, so I'm starting to think seriously about it. May I ask why you are interested in this particular algorithm?
udiprod Just because it would be interesting to see it animated, because it does not work with any rhyme or reason. It would be fun to watch.
Ok, thanks for the input. I'll certainly think about it.
I think it's about highlighting the part where bogo sort actually fails. Yes, we know the outcome that it doesn't work, but exactly at what point does it fail?
Dude7469 it doesn't "fail" so much as it's completely braindead. All it does is shuffle the objects randomly until it gets sorted by complete accident. There's really no point in animating something so stupid. Bogo sort is the worst possible sorting algorithm, but even bogo would eventually, given enough time, accidentally resort the list. If your list only had three items, for example, it would only take a few random shuffles to get it in order. But then imagine reshuffling a deck of cards over and over. You'd be shuffling those cards for billions of years before getting them back into order using bogo sort.
I watched "We are number one but every "one" is replaced by a sorting algorithm" and now this is all I get in my recommended box
It seems lately I keep getting bombarded with recommendations that are somewhat similiar to another videos watched....
「Look over here!」 we too
K
holy shit 😂
Brilliant
This is actually a really good way of explaining sorting methods.
I wanted to see Quick Sort deal with a perfectly sorted list at the beginning lol
I’ve seen multiple visualizations, code implementations, and descriptions of Merge sort before now. I still had almost no understanding of the core mechanic. After watching this video, I understand it perfectly, and see now how simple it is. This is a fantastic visualization. Thank you!
It's probably because this series of videos shows a practical way these algorithms are done. It's way easier to understand when you actually SEE it happen. You can do all of this in real life. I wish they could do this with the harder to understand sorts, like Gravity Sort.
@@uknownada Sorts like gravity involve altering the values of items instead of redistributing the items
@@uknownada Gravity sort sorts the elements by by placing beads on the first n poles for each number n in the list, then lets them fall. Simple as that.
Merge sort was taught to me with a recursive implementation from the start, and that made it very confusing (no, despite what fans of certain languages will tell you, recursion is not "actually super intuitive and efficient").
It makes so much more sense when it's first explained like this, and *then* you're shown recursive pseudocode.
@@Eknoma You could watch my video on "23 minutes of distributive sorts" and skip to the part with gravity sort. Simplified gravity is also a way of representing gravity sort
the little sound that the balls make when being pushed back on the shelf is satisfying
You know you reached the peak of entertainment when you make videos of sorting robots battling while you narrate it with the voice of someone in a child's learning program
you know your in the peak of depression when your watching 2 robots sort balls
@@MI-lo2hj ...or you are somebody from the nerd corner that wants to understand algorithms.
When introduced to the common sorts, we saw animated demonstrations much like this, with various data set sizes. With small groups, bubble sort is actually quite good. Go to 100+ in a group, and suddenly you see why it's called quicksort. With small groups, quicksort doesn't seem all that clever, but when the group size goes up, it gets very much better.
You can see in the quicksort vs bubblesort video. Already at 10 elements quicksort is much better than bubblesort:
th-cam.com/video/aXXWXz5rF64/w-d-xo.html
udiprod Then I think the 'random' group was set up. As a general rule, quicksort isn't that special on small groups. Sometimes, yes, but not consistently. Go to a bigger group, and it's blindingly obvious. It's so much better it's staggering. Also, much is made here of the number of comparisons. That alone doesn't tell the story. It's one part. Bubblesort isn't slow because of comparisons. It's slow because the number of operations is much higher. Comparisons are one operation. Quicksort seems like a somewhat more complicated algorithm, intuition wouldn't tell you how much better it is. Still, thank you for making these and sharing them.
Kneedragon1962 You are right that on very small groups quick sort's advantage won't be noticed, but on 10 it's already very much noticed. The random permutation wasn't set up.
You're also right that comparisons is not the whole story. The competition shown in the video is in fact composed of several elements. For example, it takes time for the robots to move from side to side. Interestingly, in the quick-vs-bubble competition, quicksort spends more time on moving, so you can see bubblesort makes more comparisons per-second than quick sort. This effect is sometimes seen in real life as well.
Thanks for watching and for interesting comments.
@@udiprod It would be helpful if, in the description or accompanying discussion, there's a breakdown of what represents what (for us computer nerds). For instance - what about the robot moving side to side? In the video, it seems like it's at a constant velocity, but really one would expect to see constant *travel time* (or a far more complex pattern if the dataset is bigger than the L1 cache). Clarifying the assumptions made and whatnot (just a little bit beyond what's in the discussion) would be helpful.
@@antonliakhovitch8306 agree!
*"remove the darker one"*
Okay now I'm rethinking about this video's moral lesson
@@huyphamuc6372 I don't think she means it like that
LMFAO
THATS RACIST
😂
how did i get here
lol , ikr
Sflot
Yes you did, you friccin moron.
oh fricc
It was recommended because enough people liked this video who also liked other videos with some qualities similar to other videos you have watched and liked.
The process is called collaborative filtering, which is a machine learning algorithm that infers some abstract features of a video from correlation of user preferences, and uses those features (and your preferences) to characterize you as a user.
(It is also possible that the recommendation system is content-based, i.e. meta-data associated with this video is similar to other videos you have liked or watched recently.)
Because you clicked here dummy
This is so cute.
no.
t p o s e
Loser
agreed.
The nice thing about quicksort is that once the nth pivot is correctly positioned, a 2^n-1 additional robots can be brought in to help with the sorting. As long as they stay partitioned by the positioned pivots, they will not interfere with each other.
(This of course approximates parallelized sorting using quicksort)
Uejji Mergesort can also be parallelized at the beginning and only needs to drop to single threaded in the end, kind of like quicksort but in reverse
@@AlexanderPavel and bitonic sort can always be parallelized
Uejji Except will robot A like robot B messing with his desk? I think not.
Studying computer sciences, I wished I had seen this video before, didn't really understand merge sort only by code, but this makes everything perfectly clear!
What an odd way to teach programming concepts.
it works though! :D
What an even way to teach programming concepts.
At least we get it
Especially if the language you use just has array_sort as a function and no other choice
odd? what the hell.. you will never find another more clear explanation about sorting...
me too
Donovan A S R Which match?
Same
I was Q team. I love how simple quicksort is.
@@sangramjitchakraborty7845 I think most people would say merge sort is conceptually simpler than quicksort
instead of hoping for miracle, it indirectly implies to bogo
JTX8000 xd
Bongo*
@@Fif0l bogo sort actually. OH YOU LIKE SORTING? NAME EVERY *_S O R T_*
@@AeroTheVaporeon cheeseburger sort
your method of explanation is amazing
Windows defragmenter uses merge sort. But instead of having a second shelf (or, in this case, disk) it moves files to the end of the partition, separating them using the empty space between them. That's why a good defragment process requires lots of free space.
Video: *was uploaded 5 years ago*
TH-cam algorithm 2019: *Oooooh yeah he’ll love this randomly*
But you clicked it didn't you!?
Jonty Morris 🤫 of course not
and here I am in 2021
Comment from 5 years ago now lol, means video 10 years ago
One of a better explanations I could find online. Great job. Thank you guys!
it's 2019 and I finally found a channel that animates algorithms in such an easy way. Subbed
2:18 Top 10 Anime Battles
Underrated
LMFAO
I'd actually be interested in a multi threaded comparison of this and quick sort.
Merge sort can multitask at the start (when it's just very small subsequences) to merge while quick sort can multitask at the end (because things have been partitioned)
How would they compare in best, random, and worst case permutations?
Merge would likely do better as Quicksort relies a little upon luck to find a good split for the smaller lists. Smarter Quicksorts will often pass the lowest and highest values of a list, so the recursive call can identify the average between the two values and try to use that to split the list properly. This even splitting doesn't work right if the values are 'clustered' (i.e. a list with two numbers that are less than 100, eighteen numbers that are in 100-200 range, and five numbers that are in the 201-5000 range).
Radix (MSD) could also benefit from multi-tasking, as each sub-group is then put into its own task for sorting.
Merge all the way
Sees 1st round: NOOOOOOOOOOOOOOOOOOOOOO!!!!!!!!!!!!!!!
Sees 2nd round: YEA BOIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII
And now say hello to MULTITHREADING
This is my FAVORITE out of the search algorithm visualization videos...... the sound of the balls being placed back down is so satisfying
I come back at least once a year to listen to the sound and watch the intense sorting match lol
Anyone notice that the blip noise sounds exactly like Starbound's activate computer noise?
Omg you're right haha xD
maybe it's a stock sound effect?
either way, pretty interesting.
Pretty sure they use it in the Talos Principle too.
If quicksort chooses, by random, the highest-value unsorted item in the list each time then it literally becomes bubble sort. If it randomly chooses the highest and lowest alternately, it becomes cocktail sort.
MORE! Dude! we love this, come on! You know, when you start a channel with "GOOD" videos. then you have to go on!
This is by far best way of teaching algorithm I have ever seen in my entire life
I’m so glad I found this channel. Makes me fall in love with Programming all over again when I’m losing hope
Same
I've been trying to understand the merge sort for a few weeks now, but to no avail. Who knew a robot with bowling balls was what I needed to finally get the concept?
I'd favor using merge sort over quick sort, simply because of the deterministic behavior. In one of my projects, I use sorting in a real-time system. Ensuring deterministic behavior is essential for estimating the performance and execution times of tasks.
A bit late, but if you need deterministic behavior out of quick sort, have it pick the first element of an unsorted list. Or the last.
The method of selecting the pivot is not important to it guaranteeing a sorted list at the end, but it may be paramount for sorting very quickly.
Remember, if quicksort gets lucky and evenly divides the list in half with every pivot, it gets really really good results (not sure how good though), while its worst performance is roughly on par with insertion sort (picking the an element from an unsorted list that goes either at the top or at the bottom of the sorted list, i.e. never splitting the list and only reducing its size by 1 every pass)
Merge sort is guaranteed to be O (n log n) and is a stable sort, while Quick Sort is O(n²) in the worst case.
i love this, i could watch this all day
No matter how many of these videos I watch, I still think these competitions are so funny, like is serious stuff
wow.. i could understand sorting algorithms easily. thank you!!
i wish my teacher explained like this... this video is GOLD!
best sorting visualization I have ever seen
On this week’s episode of
“Why Is This In My Recommended”
You saved my life why couldn't you be my teacher.
but...isn't that kind of difficult for public school?
@@wishmaker7863 is that supposed to be a roast ?
Cuz I'm not really sure
@@Ucefgrb there must have been a longer comment chain that's since been deleted...i honestly don't remember what i meant when writing this.
Really well done. I love the animations! Thank you
What a fantastic video, absolutely top-notch, thank you so much!
I can't process math this quickly, nor does this really mean anything to me pertaining to actual computing, but I'm on the spectrum and this is like the perfect li'l sensory video for my brain.
That merge sort robot was definitely concerned when the balls started sorting themselves.
I wanna witness the robot for Radix LSD In-place Sort (Base 10)
You kidding? Radix sort isn't based on comparisions, how do you supposed those robots to do?
@@huyphamuc6372 swish em around blindly
The screen at the front of the table should show which number each ball is, and the robot should make piles for each digit it focuses on, then dumps them back into the list in order. It starts from the last digit, and the process repeats as it works its way up
Cool channel, I nice to find this
Your demonstrations are very simple and interesting
I was on the verge of having a breakdown before watching this video (my exam is in 2 days and i still have to cram an entire semester worth of work and i don't understand shit). Thank you for this fun way of explaining this!
I never thought learning could be this interesting
I love those robots. I hope they can accompany me to my exams.
Really nice explanation, never seen more vivid one.
I'm new to programming and had problems understanding merge-sorting, how does it work and why it's efficient. Thanks to this video I answered every question in less than 5 minutes
Thank you, short sighted robots!
Top 10 epic anime battles
This is actually cool
so clear and well illustrated!
I cant believe TH-cam didn't recommend this to me for TEN YEARS!!!.
Can quick sort be adjusted to shoot for the average pivot? Say it surveys the data it has, finds the min and max, and averages that out and then uses the closest value for its first pivot? I'm sure this has already been thought up long ago - if so, what's it called?
giruppy Yes, there are all kinds of variants of this type. You can see here: en.wikipedia.org/wiki/Quicksort#Choice_of_pivot
Actually finding the min and max as you suggest might work, but it will be more costly. An even more costly solution is to actually find the median, which is the optimal choice. There's an efficient way to do it in O(n) time, which yields a quicksort with guaranteed O(nlogn) runtime. But in practice (for reasonably sized n) it works much slower. See here en.wikipedia.org/wiki/Median_of_medians
Quicksort is much faster in practice, and it is not only because memory consumption is lower but also because by using randomized algorithms you can choose an optimal pivot.
Regular quicksort is O(n^2) worst case probably regardless of pivot choice. Randomized pivots make it a probably 1 in O(n) chance of it being the worst case. Try finding a good pivot for inputs that involve both halves or each quarter being already sorted and also perfectly linear instead of wrinkly. You're also right in some ways about it being faster in practice, as standard programming languages use it or variants as their default sort and merge sort or variants as their default stable sort. Some like Python only use merge sort or variants. Some variants of quicksort like introsort (default sort of C++ and C#) alleviate the worst case by using heap sort, or Java (at least OpenJDK) uses a dual-pivot quicksort. Partitions can be done by medians or something instead of particular items. There's a small but talented and active group by Musicombo that's dedicated to making sorting algorithms, either for fun or as serious and fast algorithms
I love that instant replay on the sorting robots
These videos are fantastically informative! A video on of big O notation would be greatly appreciated.
Both sorts are O(n log n) average case, and it's merge sort's worst case. Quick sort's worst case is O(n^2).
12:30 am and this stuff is exciting...
It's even more exciting at 1:54am
Is it me or these robots are so cute?
these videos are actually very helpful
watching this videos with no sound makes them into surreal mysteries
O god
It is very helpful for me to visualize them. I hope you could do the same for other algorithms as well. Two thumbs up !! (4 if you want to count toes XD)
I dont know what is happening but i kinda like it
Put this series on the tv and boys will cheering on their favorite robots. Fights will be started over wrong predictions.
Me who accidentally saw a couple shorts and vids about sound of sorting and now this is the 10th sorting video today
Where were you when I failed my Data Structures and Algorithms exam?
Probably programming the robots.
I love the subtle accent of the narrator. There's some accent that she was trained out of but I really want to hear it more...
I would love to see these as a kid! So fancy.
Finally, something that helps you understand what actually goes on
I didn't know that I was starving till I tasted you
no
What if you use Quick Sort for the first level and Merge Sort for the others?
+fabts4 This will create hybrid algorithm whose statistics are somewhere in between that of quick sort and merge sort (e.g., somewhat more comparisons than merge sort, but a little less than quick sort). Usually quick sort is combined that way with another algorithm: insertion sort, since it performs less swaps.
+udiprod Haven't seen insertion sort on the chanel...
+fabts4 Yes, right. I actually plan to do it sometime. Hopefully this year.
There's probably a linear time algorithm that can determine if Merge or Quicksort is better.
This is ADORABLE! I love this 💕
Very nicely explained. Very nice to watch.
Im your 3000th SUB :DDDDDD
Thanks! :)
Nobody:
TH-cam recommended at 12am:
I didn't care about sort algorithms. I stayed here to watch those cute robots.
Merge sort can actually alternate the shelf its using to optimize moving the elements (in addition to the optimization listen in the article). How much would that increase Merge Sort by?
Actually Merge sort can choose to in-place Merge the first 2 Elements based upon if it would need to move the elements on the last merge again, which would only happen if there is an odd number of recursion steps.
How about radix sort and bucket sort?
guys I think I found a way to make the sorts much faster: fix your robot's short-sightness.
lmao
And what would you do then?
Look at them all, and put the darkest at the front, and repeat?
Selection sort.
@@thehiddenninja3428 with fixed short-sightness that would be parallel selection sort
Thank you for the great videos!
Wow, this teached way better than on my university back in the day.
Phew, for a second I thought that merge would win! #teamquick
Edit: oh no, I celebrated too early
You talk like asian reporter Tricia Takanawa.
family guy lol
My 2021 is off to a great start
I watched one sorting algorithm video for some reason and now my whole recommended this filled with this
EPIC animation work bro ! nice :-)
awesome way to explain algorithm.. :) very well animated. Definitely recommend! (y)
the match of the century
You make sorting algorithms seems like competitors in some obscure Olympics sport.
this is amazing!
Thanks for the demonstration.
Nicely done!!
GREAT Videos man!!! Thank so much!!
WE NEED MORE SORTS!
I think this is an awesome visual representation of sorting. How many screeching line sorts can one watch?
You know you're life is failing when you're cheering on a sorting robot
I love your videos!