Merge Sort vs Quick Sort
Ғылым және технология
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
Пікірлер: 907
“Instead of relying on miracles...” Bogo sort: 😥
@XPForever
3 жыл бұрын
XD
@astro_cat030
Жыл бұрын
its rare
@tesseract7586
Жыл бұрын
yes that is true
@xevento8682
Жыл бұрын
MiracleSort: 😥
@nif0
Жыл бұрын
@@astro_cat030 you just don't believe enough
"hey dude what sports do u watch" me: *_sweats nervously_* thx my folks for the correction
@mariafe7050
4 жыл бұрын
me: Sorting algorithms! "what"
@mariafe7050
4 жыл бұрын
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?
@xl000
4 жыл бұрын
said who ?
@whiskeyburns5230
4 жыл бұрын
lets play cricket
@mryup6100
4 жыл бұрын
@Commenter in a Box r/wooosh time!
Can we get bogosort?
@udiprod
7 жыл бұрын
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?
@kenners1993
7 жыл бұрын
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.
@udiprod
7 жыл бұрын
Ok, thanks for the input. I'll certainly think about it.
@Dude7469
7 жыл бұрын
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?
@ophello
7 жыл бұрын
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?
@StevenAkinyemi
7 жыл бұрын
Gretgor LOL Everything basically.
@GretgorPooper
7 жыл бұрын
I know that.
@zzZAnubisZzz
5 жыл бұрын
@@GretgorPooper How wrong is your life now? Doing any better?
@daydodog
5 жыл бұрын
are you at least a compsci student?
@bukujuku1541
5 жыл бұрын
@@daydodog electrical engineering do this aswell
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!
@uknownada
4 жыл бұрын
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.
@smaybius
2 жыл бұрын
@@uknownada Sorts like gravity involve altering the values of items instead of redistributing the items
@Eknoma
2 жыл бұрын
@@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.
@antonliakhovitch8306
Жыл бұрын
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.
@smaybius
Жыл бұрын
@@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
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
@tttc
7 жыл бұрын
It seems lately I keep getting bombarded with recommendations that are somewhat similiar to another videos watched....
@AlexVasiluta
7 жыл бұрын
「Look over here!」 we too
@josgeerink9434
7 жыл бұрын
K
@mybloodymemory
6 жыл бұрын
holy shit 😂
@cutekitty2358
6 жыл бұрын
Brilliant
*"remove the darker one"*
@huyphamuc6372
4 жыл бұрын
Okay now I'm rethinking about this video's moral lesson
@TheZincMaster-on1fy
4 жыл бұрын
@@huyphamuc6372 I don't think she means it like that
@oscarnival6164
4 жыл бұрын
LMFAO
@mtsimlover2
4 жыл бұрын
THATS RACIST
@monickverma2944
4 жыл бұрын
😂
This is actually a really good way of explaining sorting methods.
@vekmogo
8 ай бұрын
I wanted to see Quick Sort deal with a perfectly sorted list at the beginning lol
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.
@udiprod
9 жыл бұрын
You can see in the quicksort vs bubblesort video. Already at 10 elements quicksort is much better than bubblesort: kzread.info/dash/bejne/k4yMubqzZdWsZpc.html
@Kneedragon1962
9 жыл бұрын
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.
@udiprod
9 жыл бұрын
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.
@antonliakhovitch8306
Жыл бұрын
@@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.
@ashutoshmahapatra537
Жыл бұрын
@@antonliakhovitch8306 agree!
the little sound that the balls make when being pushed back on the shelf is satisfying
This is so cute.
@user-nl3cf9kn6v
4 жыл бұрын
no.
@SRBAnimate
4 жыл бұрын
t p o s e
@alanbam5590
4 жыл бұрын
Loser
@sirisoj
3 жыл бұрын
agreed.
how did i get here
@einsteinsemut
8 жыл бұрын
lol , ikr
@aurelia65536
7 жыл бұрын
Sflot Yes you did, you friccin moron.
@KEL5isGodrules
7 жыл бұрын
oh fricc
@lelcat8414
6 жыл бұрын
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.)
@mariafe7050
5 жыл бұрын
Because you clicked here dummy
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
@MI-lo2hj
3 жыл бұрын
you know your in the peak of depression when your watching 2 robots sort balls
@torkakarshiro5170
Жыл бұрын
@@MI-lo2hj ...or you are somebody from the nerd corner that wants to understand algorithms.
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)
@AlexanderPavel
7 жыл бұрын
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
@groszak1
5 жыл бұрын
@@AlexanderPavel and bitonic sort can always be parallelized
@MinecraftLD10
4 жыл бұрын
Uejji Except will robot A like robot B messing with his desk? I think not.
What an odd way to teach programming concepts.
@dcs_0
6 жыл бұрын
it works though! :D
@abandoned7501
5 жыл бұрын
What an even way to teach programming concepts.
@Chowow
5 жыл бұрын
At least we get it
@bigdoggetom6549
5 жыл бұрын
Especially if the language you use just has array_sort as a function and no other choice
@gstkrr8
5 жыл бұрын
odd? what the hell.. you will never find another more clear explanation about sorting...
@user-ll7kq7ne4d
6 жыл бұрын
me too
@mariafe7050
5 жыл бұрын
Donovan A S R Which match?
@dancingbread7015
5 жыл бұрын
Same
@sangramjitchakraborty7845
4 жыл бұрын
I was Q team. I love how simple quicksort is.
@dv_xl
4 жыл бұрын
@@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.
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!
your method of explanation is amazing
Video: *was uploaded 5 years ago* KZread algorithm 2019: *Oooooh yeah he’ll love this randomly*
@jontymorris8200
5 жыл бұрын
But you clicked it didn't you!?
@campbellmcternan3902
5 жыл бұрын
Jonty Morris 🤫 of course not
@DocktorFurioustank
3 жыл бұрын
and here I am in 2021
@user-zi7kp8un3s
20 күн бұрын
Comment from 5 years ago now lol, means video 10 years ago
@campbellmcternan3902
15 күн бұрын
@@user-zi7kp8un3s that's crazy thanks for reminding me :)
One of a better explanations I could find online. Great job. Thank you guys!
2:18 Top 10 Anime Battles
@bebel9349
4 жыл бұрын
Underrated
@bayram00
3 жыл бұрын
LMFAO
it's 2019 and I finally found a channel that animates algorithms in such an easy way. Subbed
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?
@toddkes5890
Жыл бұрын
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.
instead of hoping for miracle, it indirectly implies to bogo
@MiguelX413
6 жыл бұрын
JTX8000 xd
@Fif0l
4 жыл бұрын
Bongo*
@AeroTheVaporeon
4 жыл бұрын
@@Fif0l bogo sort actually. OH YOU LIKE SORTING? NAME EVERY *_S O R T_*
@anhbui-bc4ew
3 жыл бұрын
@@AeroTheVaporeon cheeseburger 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.
@ferociousfeind8538
Жыл бұрын
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)
@Carlos-ux7gv
9 ай бұрын
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.
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
This is by far best way of teaching algorithm I have ever seen in my entire life
Merge all the way Sees 1st round: NOOOOOOOOOOOOOOOOOOOOOO!!!!!!!!!!!!!!! Sees 2nd round: YEA BOIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII
@guy7329
3 жыл бұрын
And now say hello to MULTITHREADING
Anyone notice that the blip noise sounds exactly like Starbound's activate computer noise?
@xianchen1935
5 жыл бұрын
Omg you're right haha xD
@mozarteanchaos
3 жыл бұрын
maybe it's a stock sound effect? either way, pretty interesting.
@nathancollins1715
2 жыл бұрын
Pretty sure they use it in the Talos Principle too.
i love this, i could watch this all day
I’m so glad I found this channel. Makes me fall in love with Programming all over again when I’m losing hope
@ricj9594
3 жыл бұрын
Same
wow.. i could understand sorting algorithms easily. thank you!!
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.
best sorting visualization I have ever seen
What a fantastic video, absolutely top-notch, thank you so much!
i wish my teacher explained like this... this video is GOLD!
Really well done. I love the animations! Thank you
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!
Cool channel, I nice to find this Your demonstrations are very simple and interesting
MORE! Dude! we love this, come on! You know, when you start a channel with "GOOD" videos. then you have to go on!
I wanna witness the robot for Radix LSD In-place Sort (Base 10)
@huyphamuc6372
4 жыл бұрын
You kidding? Radix sort isn't based on comparisions, how do you supposed those robots to do?
@fuitbythefoot
4 жыл бұрын
@@huyphamuc6372 swish em around blindly
@smaybius
3 жыл бұрын
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
No matter how many of these videos I watch, I still think these competitions are so funny, like is serious stuff
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.
You saved my life why couldn't you be my teacher.
@wishmaker7863
7 жыл бұрын
but...isn't that kind of difficult for public school?
@Ucefgrb
4 жыл бұрын
@@wishmaker7863 is that supposed to be a roast ? Cuz I'm not really sure
@wishmaker7863
4 жыл бұрын
@@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 never thought learning could be this interesting
I think this is an awesome visual representation of sorting. How many screeching line sorts can one watch?
I love that instant replay on the sorting robots
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?
@udiprod
9 жыл бұрын
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'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?
Really nice explanation, never seen more vivid one.
Hey! I know, the video is 5 years old, but can you please make the double selection sort? I've watched some sorting algorithm videos, and somehow the double selection sort was the quickest of them all.
I love those robots. I hope they can accompany me to my exams.
That merge sort robot was definitely concerned when the balls started sorting themselves.
these videos are actually very helpful
so clear and well illustrated!
Top 10 epic anime battles
On this week’s episode of “Why Is This In My Recommended”
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.
These videos are fantastically informative! A video on of big O notation would be greatly appreciated.
@smaybius
2 жыл бұрын
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).
This is actually cool
I dont know what is happening but i kinda like it
Finally, something that helps you understand what actually goes on
Hey what sports u watch? "Its complicated"
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.
@smaybius
2 жыл бұрын
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
Is it me or these robots are so cute?
I would love to see these as a kid! So fancy.
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!
What if you use Quick Sort for the first level and Merge Sort for the others?
@udiprod
8 жыл бұрын
+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.
@fabts4
8 жыл бұрын
+udiprod Haven't seen insertion sort on the chanel...
@udiprod
8 жыл бұрын
+fabts4 Yes, right. I actually plan to do it sometime. Hopefully this year.
@JM-us3fr
6 жыл бұрын
There's probably a linear time algorithm that can determine if Merge or Quicksort is better.
12:30 am and this stuff is exciting...
@blitzbigboi7613
4 жыл бұрын
It's even more exciting at 1:54am
What if the list was already completely sorted, how would that comparison be?
Taking robot movement into account, which sorting algorithm should be the best?
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)
How about radix sort and bucket sort?
My 2021 is off to a great start
Very nicely explained. Very nice to watch.
Im your 3000th SUB :DDDDDD
@udiprod
9 жыл бұрын
Thanks! :)
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...
Great video. Thank you. Do you mind if I ask how did you get this animation ? Thanks. Once again
@udiprod
9 жыл бұрын
Walter Muzazaila Sure, thanks. I created this animation using a tool called Maya.
I cant believe KZread didn't recommend this to me for TEN YEARS!!!.
Where were you when I failed my Data Structures and Algorithms exam?
@ravelterthetraveler
3 жыл бұрын
Probably programming the robots.
I didn't know that I was starving till I tasted you
@microwavedkoolaid9193
4 жыл бұрын
no
Where can I buy that 🤖
watching this videos with no sound makes them into surreal mysteries
@ItsJJOLO
4 жыл бұрын
O god
Nobody: KZread recommended at 12am:
Phew, for a second I thought that merge would win! #teamquick Edit: oh no, I celebrated too early
This is ADORABLE! I love this 💕
the match of the century
guys I think I found a way to make the sorts much faster: fix your robot's short-sightness.
@taureon_
5 жыл бұрын
lmao
@thehiddenninja3428
5 жыл бұрын
And what would you do then? Look at them all, and put the darkest at the front, and repeat? Selection sort.
@groszak1
5 жыл бұрын
@@thehiddenninja3428 with fixed short-sightness that would be parallel selection sort
You talk like asian reporter Tricia Takanawa.
@ItsRawrTopia
5 жыл бұрын
family guy lol
What kind o tv program from the future show robots competing sorting algorithms?
is this related to that video of shrieking black lines that i watched a couple days ago?
I didn't care about sort algorithms. I stayed here to watch those cute robots.
thank you a lot. this video helps a lot to understand the concept crystal clear for poor student like me.
is there a merge sort vs bubble sort
Could you do LSD Radix Sort next?
What does merge do when the sequence is not a power of 2?
Me who accidentally saw a couple shorts and vids about sound of sorting and now this is the 10th sorting video today
May we get a new type of sort like a base 10? Sort?
Does anyone know what engine the visualization/graphics were made in?
@udiprod
4 жыл бұрын
It was made with Maya