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 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
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?
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.
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
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: ua-cam.com/video/aXXWXz5rF64/v-deo.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.
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)
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.)
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!
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.
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
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.
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.
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)
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
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 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'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!
I think there’s a variant of quicksort that DOESN’T choose pivots/partitions at random, it always chooses the middle element in the list, then their sublists and so on
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 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.
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
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)
+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.
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.
the reason that merge does so much better than quick in the worst-case test is that in quicksort, every element has to be compared against almost every other element (in true worst-case, it would be every element compared against every other). in merge, however, even with the maximum number of comparisons per level (where all the lists of 1 are merged before any of the lists of 2), the number of comparisons is never more than the number of elements, but the number of levels only grows logarithmically (that is, the number of levels increases by 1 with each power of 2 elements you pass)
I'm disappointed that they didn't bother addressing how we know lists of size 1 are already sorted. But not as disappointed as I am in the functionality this video lost when annotations were disabled.
one of the issues with merge sort is the increased memory usage it inherently needs. it requires 2 full sized heaps of memory equal in size to the list
Don't forget that mergesort requires additional memory. Quicksort is in-place. So if you have to do lots of sorting continuously, and your programming language is garbage collected, quicksort will be a better choice, because it won't be over-allocating and stressing out the memory manager. Hence in the majority of standard libraries across programming languages, quicksort is the default sorting algorithm.
![[Laser] Firing squad synchronization problem](/img/n.gif)
"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’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
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 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
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
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:
ua-cam.com/video/aXXWXz5rF64/v-deo.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!
the little sound that the balls make when being pushed back on the shelf is satisfying
*"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
😂
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.
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
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...
Video: *was uploaded 5 years ago*
UA-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
@@user-zi7kp8un3s that's crazy thanks for reminding me :)
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
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.
your method of explanation is amazing
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
One of a better explanations I could find online. Great job. Thank you guys!
2:18 Top 10 Anime Battles
Underrated
LMFAO
it's 2019 and I finally found a channel that animates algorithms in such an easy way. Subbed
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
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.
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.
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’m so glad I found this channel. Makes me fall in love with Programming all over again when I’m losing hope
Same
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.
Put this series on the tv and boys will cheering on their favorite robots. Fights will be started over wrong predictions.
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
This is by far best way of teaching algorithm I have ever seen in my entire life
That merge sort robot was definitely concerned when the balls started sorting themselves.
No matter how many of these videos I watch, I still think these competitions are so funny, like is serious stuff
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?
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.
i wish my teacher explained like this... this video is GOLD!
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!
wow.. i could understand sorting algorithms easily. thank you!!
You know you're life is failing when you're cheering on a sorting robot
MORE! Dude! we love this, come on! You know, when you start a channel with "GOOD" videos. then you have to go on!
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!
On this week’s episode of
“Why Is This In My Recommended”
watching this videos with no sound makes them into surreal mysteries
O god
I never thought learning could be this interesting
I think there’s a variant of quicksort that DOESN’T choose pivots/partitions at random, it always chooses the middle element in the list, then their sublists and so on
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 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.
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
I cant believe UA-cam didn't recommend this to me for TEN YEARS!!!.
Really well done. I love the animations! Thank you
Merge sort is definitely my favorite now, I like the way it thinks
I love those robots. I hope they can accompany me to my exams.
Finally, two with opponents. Their battle will be legendary!
I show these to my dog hes learning how to write javascript
i love this, i could watch this all day
Top 10 epic anime battles
Not what I had in mind when I searched for “merge sort vs quick sort” but still helpful.
Where were you when I failed my Data Structures and Algorithms exam?
Probably programming the robots.
I would love to see these as a kid! So fancy.
Is it me or these robots are so cute?
Thanks! Now my friends are gonna call me a wizard when I sort a deck of cards in half a second.
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)
Me who accidentally saw a couple shorts and vids about sound of sorting and now this is the 10th sorting video today
I dont know what is happening but i kinda like it
I love that instant replay on the sorting robots
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.
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.
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...
the reason that merge does so much better than quick in the worst-case test is that in quicksort, every element has to be compared against almost every other element (in true worst-case, it would be every element compared against every other). in merge, however, even with the maximum number of comparisons per level (where all the lists of 1 are merged before any of the lists of 2), the number of comparisons is never more than the number of elements, but the number of levels only grows logarithmically (that is, the number of levels increases by 1 with each power of 2 elements you pass)
This is actually cool
how did i get on this side of youtube i just wanted to watch some colors get sorted all funky like one time and now this is my whole feed
0:36 “... and remove the darker one”. r/HolUp
I didn't care about sort algorithms. I stayed here to watch those cute robots.
I didn't know that I was starving till I tasted you
no
I'm disappointed that they didn't bother addressing how we know lists of size 1 are already sorted. But not as disappointed as I am in the functionality this video lost when annotations were disabled.
It's self-explanatory that a list of size 1 would be sorted. What element is going to be out of order? There's only one.
@@michawhite7613 What can I say, I like rigorous proofs of the obvious. It's the difference between knowledge and understanding.
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
I don't know which is more intriguing, why is this in my recommended or why is this so oddly interesting
How about radix sort and bucket sort?
Request: Do weave sort.
It interleaves the merged lists and then uses insertion sort on the interleaved list.
Im your 3000th SUB :DDDDDD
Thanks! :)
this gives off strong vibes of being an educational video made for schoolchildren in 1994
Phew, for a second I thought that merge would win! #teamquick
Edit: oh no, I celebrated too early
one of the issues with merge sort is the increased memory usage it inherently needs. it requires 2 full sized heaps of memory equal in size to the list
Nobody:
UA-cam recommended at 12am:
best sorting visualization I have ever seen
You talk like asian reporter Tricia Takanawa.
family guy lol
So merge is quicker than quick.
*Wow this is mind blowing*
Really nice explanation, never seen more vivid one.
You make sorting algorithms seems like competitors in some obscure Olympics sport.
My 2021 is off to a great start
I think this is an awesome visual representation of sorting. How many screeching line sorts can one watch?
The sound of the balls being pushed back to the bottom shelf is so satisfying
Finally, something that helps you understand what actually goes on
すげぇな、場合によってこんなに差出るのね。それにしても、ロボットが一生懸命ソートしているの可愛い。
How come this is the first time I stumble upon this channel?
*The time complexities are*
Best: O(nlogn)
Average: O(nlogn)
Worst: O(nlogn)
Storage: O(n)
Don't forget that mergesort requires additional memory. Quicksort is in-place. So if you have to do lots of sorting continuously, and your programming language is garbage collected, quicksort will be a better choice, because it won't be over-allocating and stressing out the memory manager. Hence in the majority of standard libraries across programming languages, quicksort is the default sorting algorithm.
Merge sort can be done in-place too