Quicksort vs Mergesort in 35 Seconds

Sort 200 different colors in under 30 seconds #shorts
Quick sort and Merge sort are used. We see that quicksort takes fewer operations here, but some of that could be how I counted the operations. Quicksort is known for being the fastest though.
Quicksort work by selecting a pivot value and putting everything less than (or equal to) that pivot to the left of it in the array, and everything greater than the pivot to the right of it.
Merge sort works by recursively splitting the list until it has two lists with only one element in them, and then merging them together in the correct order.
Both of these are n log n time. My quicksort implementation doesn't use extra storage, my merge sort implementation does make slices of the list when it is splitting.
This was done using python & pygame
All code
Copyright 2021 Google LLC
SPDX-License-Identifier: Apache-2.0
www.apache.org...
The inspiration for this code was this github repo
github.com/Luc...
I used this algorithm to turn a wavelength into an RGB color
www.noah.org/wi...
Thumbnail Background image (Thunderstorm) by FelixMittermeier
pixabay.com/ph...

[@xTriplexS]

I mean, Quick Sort depends on your pivot but Merge Sort will always be consistent

[@vwlz8637]

Merge sort sucks. It only works with randomised data.

[@yessure5792]

@@vwlz8637it can be hugely parallelized though

[@d_breadstix_guy1603]

@@vwlz8637isn’t randomised data the data you’ll mainly be working with?

[@blacklight683]

@@vwlz8637 isnt that the point? why would you need to sort non random data? unless you mean put new data in the right place but that's literally not its job

[@icarodlima]

@@vwlz8637 gotta be kidding 😂

[@aojntm7596]

Oh hell yeah finally RUclips is recommending me good shit

[@dubiouscode4802]

Yeah, I think the recommendation algorithm is based on Bubble sort, so it takes while :)

[@bepeplia5086]

@@dubiouscode4802 great humour right there

[@justtavi1238]

​@@dubiouscode4802No it's based on bogosort cause everything is random😂

[@shaurryabaheti]

​@@dubiouscode4802nah nah it's selection sort 😂

[@fruta6279]

@@shaurryabaheti its stupid sort lol

[@wojteksowinski248]

One thing a lot of people forget when comparing these two is that quick sort can be implemented as an in-place sort with less memory allocation required. That's one of the main reasons it ends up being faster in practice despite having a higher worst-case complexity.

[@theolinder676]

Nobody talk about parallelization. Merge sort is the default implementation for modern language because it can be parallelized, and, therefore, faster

[@Alpacaluffy]

This. Divide and conquer.
**Multiply and surrender.**

[@finbar163]

Quicksort can be parallelized

[@pram2000]

And it can better use cpu caches

[@marble17]

> I bet on Merge Sort
> I lost my money

[@Hi-Im-Noob-uwu]

To who?

[@marble17]

@@Hi-Im-Noob-uwu MERGE SORT, HE LOST, I BET $1M ON THAT (joking)

[@keanugaming2687]

​@@marble17i bet 10 bucks on quick sort and won 20 bucks

[@lenoobxd]

bro did not go big

[@marble17]

@@lenoobxd go big or go home
I go home

[@moveonvillain1080]

Mergesort is always O(n*log(n)) but and Quicksort is mostly O(n*log(n)) in worst case it can go to O(n^2).
However if both run in their ideal time complexity of O(n*log(n)) then Mergesort just has a bigger constant hence the slowness.

[@simohayha6031]

Merge is also more space costly

[@ocaly]

​@@simohayha6031 depends on your data structure.

[@polybay]

i am a simple man. i see computer video, i click

[@BobChess]

Quick sort is fast but the worst case is O(n²). Mergesort is just more consistent.

[@Vzduch2]

Quicksort is also O(nlogn) if you use a function to find the median for your pivot. But in practice it's much faster to get a random pivot or a median of medians.

[@bitonic589]

@@Vzduch2 what about uniform data?
rip n log n

[@Vzduch2]

@@bitonic589 O(nlogn)

[@Aloyz3n]

quick sort is O(n^2) for particularly unlucky input data. it basically turns into insertion sort

[@saurabhgade781]

Especially already sorted data.

[@darknight3613]

That's why we live it for the random gods.
You can't be unlucky hundreds of times in a row so its always nlogn.
I think it's safe to bet you won't come across a case of true n² in your life.

[@Aloyz3n]

@@darknight3613 not every data you sort is randomly shuffled, n² can happen for A-shape, V-shape or data that is already sorted (depending on quick sort pivot implementation) and these data orders aren't that rare when you measure some real-life properties; heck if you sort something twice by accident and take your pivot at a wrong spot you'll get n²;
so I don't think it's just a theoretical, it's something to keep in mind; but fortunately vast majority of programers can rely on built-in sorting functions and have other people worry about low-level implementation

[@acasualviewer5861]

unlike mergesort, quicksort isn't stable
unlike quicksort, mergesort requires o(n) additional storage to work

[@alyx6427]

quick sort also is nice if you might need to get the list in whatever order it is before finishing, like the list ends up mostly finished soon and just perfects it

[@santitabnavascues8673]

Quicksort is rarely used in its pure form, it resorts to other algorithms when it detects its performance is degrading, or when the set size is just so small that the asymptotic behavior favors another algo.

[@Namelessstew]

I feel like ive entered a side of the internet that I'll never comprehend any thing more than the tickle sorting algorithms give my brain when you hear and see the lines being organized. Reminds me off arcades as a kid.

[@AdhocSyndicate]

One of the solutions I've seen to both algorithms' struggles with nearly-sorted data is to quickly shuffle the list.

[@godoegyhazi]

Bro doing RUclips Sorts

[@six-winged-juni]

at first i misread this and was wondering what the joke was aside from the ytber doing youtube shorts. you got me, gj

[@rainhat1]

😆

[@justussneary19]

I will always like merge sort more than quick sort. It seems more elegant even though it is the slower of the two

[@thomasko0947]

in the avarage case they are both the same. But quicksort can somteimes be quicker

[@notwithstanding02]

@@thomasko0947 QuickSort would be slower in the worst case

[@flazerrazer2992]

merge sort also uses more memory because it has to make a lot of extra copies of the data but quick sort is purely done in place

[@keng_aust]

@@flazerrazer2992 memory needed is just one more array with the size of the array you already have.

[@alexkelley8342]

@@thomasko0947 not entirely true. the constant factors go away when you do big-o analysis, so they're both O(n*log(n)) in the average case, but the constant factors for quicksort are smaller so its average case is mathematically faster.

[@Blorpyo]

I only trust Bogo sort

[@gr.4380]

all hail bogo sort superiority
O(n) best case, no other sorting algo can beat it

[@notjebkerman6207]

@@gr.4380 Stalin sort is O(n) in all cases.
Well, O(initial n) in all cases.

[@bitonic589]

@@gr.4380 almost every distribution sort is O(n) in almost all cases

[@Somethingsomethingyoutube]

I still love the orderliness of Radix Sort.

[@Hello2U4s0e4r]

Really helpful comparison, thank you!

[@R2Bl3nd]

The quickness of quicksort or any sorting algorithm depends on the order of the initial list; it might be quicker for a completely randomly shuffled list, but and other scenarios it might not be as quick. That's why a completely randomly sorted list is not a comprehensive demonstration or comparison.

[@JohnDVil]

Quick sort CAN be faster, but merge has more consistency among n objects, quick could get all in one, it could get only 2, the pivot is RANDOM, higher his lower lows.

[@unnamedtoaster]

Interesting, it should be obvious that algorithms with the same time complexity don't necessarily run in the same amount of time, but it's nice to be reminded.
Reminds me how for a class we had an assignment that checked if our code was linear time complexity by just timing it to see if it was fast enough. My code was linear time complexity but still not fast enough. Rather frustrating but it pushed me to come up with an even better solution!

[@deleater]

"algorithms with the same time complexity don't necessarily run in the same amount of time"
Could this be because of the different amount of times for constants (C1, C2, etc)?

[@notjebkerman6207]

Virgin Big-O purist vs Chad clock cycle counting.

[@abduallahmustafa1029]

Try edge cases

[@TyTy-gm8yb]

Depends on the imput size.....Merge sort has an O(N Log(N)) timpe comexity, which is constant.....whereas Quicksort is not doing this in a constant time....and it is dependant on the imput size

[@reedoken6143]

quick sort is also O(nlogn) provided that the pivot is the median, which is obtainable. neither is constant

[@TyTy-gm8yb]

@reedoken6143 According to Harvard, Merge Sort has a constant time in the best case and worst-case scenario. Therefore, the Merge Sort algorithm runtime is considered constant. If it wouldn't be like this, everyone would use Quick Sort instead of Merge Sort.

[@reedoken6143]

@@TyTy-gm8yb yes, merge sorts best and worst case are both O(nlogn), but O(nlogn) isn't constant. They're both dependent on their input size, that's what the n is inside O(...), n is the input size. Provided you find the median value of your list prior to sorting, quick sort also performs in O(nlogn) and can even perform in O(n). the reality is that they perform the same in 99% of situations, and the decision can be made on other factors like parallelization or memory limitations.

[@TyTy-gm8yb]

@@reedoken6143 Is constant in relation to the input size....because the time complexity is calculated in relation with the input size

[@reedoken6143]

@@TyTy-gm8yb That's not how big O notation works... f(x) = x is only constant if x is constant and is not a variable. Same thing applies to O(n). Considering the input size of the list is variable, we aren't working with just one size of list, then O(n) or O(nlogn) is not constant because n is not constant.
If constant was in relation to the input size, then quick sort would be constant also. Again, for the average case both merge sort and quick sort are O(nlogn). Quick sort simply has more variability as it is best case O(n) and worst case O(n^2), but for the majority of real world cases is O(nlogn), the same as merge sort

[@doomse150]

Really cool demonstration. I personally think merge sort animations look a bit cooler when it's done in a breadth-first ordering instead of the depth-first ordering you showed here. It still looks cool, though.

[@deytulsi18]

Quick sort is tail recursive (i.e the last statement in the recursive function is the recursive call) maybe that's the reason for it being faster than merge sort.

[@ooo8188]

What? I thought tail recursion was to reduce memory usage?

[@tzbq]

​@ooo8188 yeah I dont think it has anything to do with it but in general they're both O(nlogn) so it doesn't really matter anyway

[@PriyambodoArundayaSatmika]

You can write merge sort in tail recursion too btw

[@-blank-]

Its also faster​@@ooo8188

[@JoMama-np3og]

Quick sort is quick sort for a reason

[@bitonic589]

yeah because its trash

[@donovanmahan2901]

"Yeah operational complexity is important when it comes to scalability but we shouldn't forget about the coefficients, or any adversarial cases for that manner"

[@ShortFilmVD]

In the real world, we often know some things about our data or its existing potential orderings, influencing our choice of sorting algorithm, sometimes surprisingly so

[@Abstract_zx]

now do a 3 way comparison of a bunch of nlogn sorting algorithms. Mergesort, quicksort, heapsort, etc.

[@kmktruthserum9328]

It's like my mom always said when I was cleaning my room, only pick things up once and put them in their place so you don't have to do it again.
Unfortunately for her the place I would be putting some things was also a mess so I would have to set stuff down to clean the other area in order to be able to have room to put the item that was out of place in place 😂

[@hillstrong715]

Try doing both sorts on data sets that cannot fit in memory.

[@CarrotCakeMake]

Actually quicksort and mergesort are basically the same algorithm. Try running an ideal mergesort on a 2^n permutation, then run stable quicksort on the same permutation inverse and look at the decision tree. Exactly the same set of comparisons and moves, but in opposite time.

[@user-lh5hl4sv8z]

2 good sorts: the best short

[@jasonanthony166]

Quick sort is soooo much easier to write code for. It is naturally recursive and the code is short and beautiful 😍
The disadvantage is that a large list can cause the program stack to overflow 😢

[@jiayouchinese]

Merge sort seems more intuitive and easier to understand for me

[@obaialhaidari]

Great video!

[@bobingstern4448]

Nice!

[@dubiouscode4802]

Thanks! Welcome to the channel

[@AkmalZaini-po3bh]

@@dubiouscode4802 Hi

[@dubiouscode4802]

@@AkmalZaini-po3bh Hello!

[@MangoGoesOwO]

very interesting :)

[@georgplaz]

quicksort worst case performance is O(n²), while mergesort is O(n*log n), which is less.

[@toddkes5890]

Try doing this with Bubble Sort vs Stooge Sort
(Stooge sort = sort top 2/3 of the list, then the bottom 2/3, then the top 2/3. Named after how the Three Stooges would hit each other back and forth)

[@MC-Minority]

*than
But thx for your comment 😌

[@harshkumarsinha1865]

But quick sort can go upto n² in worst case but not the merge sort

[@shivjain]

Thanks

[@CatDaiGia123]

How about quickscramble and mergescramble

[@hobocraft0]

Quick sort of nice because it's also human based too.

[@tylerbakeman]

Quicksort has its weaknesses. Merge sort also has the ability to combine arrays- which is pretty unique
Interesting idea:
Which array is ~more sorted after N steps in the sorting? Quick sort, for sure.

[@Neokain]

I mean, that's where the name mergesort comes from. It merges arrays. It being slower on average and taking up more space needs to be taken into consideration when using it, it being stable and having a const runtime on an array of size n has its benefits. When more specific requirements are known neither standard implementations of quick- or mergesort will perform as good as optimized variations of those or other sorting algorithms

[@nikhilsultania170]

Now try them on a sorted array 😁

[@deltaidk.]

“finally, some good fucking content”

[@MusicListener-bl4hx]

"Written in Python3" runtime -> O(n³)

[@kingenzo813]

Sort lore

[@sebastiangudino9377]

Quick sort will be faster a lot of times. Merge sort will be fast all of the time

[@tachles_math]

Why tho?
Mergesort =always nlogn time complexity
Quicksort = could be (and most of the time is) nlogn time complexity but could also be O(n^2) in the worst case.
How come quicksort is better?

[@Hys-01]

should specify that nlogn refers to average case, to avoid confusions

[@TrisJC_XD]

is it me but... THE FIRST FRAME TEMINDS ME OF BAD APPLE

[@unknown_unva_brine2v]

Bead and cycle?

[@Lego_sun_wukong]

He should have use stalin sort

[@everesthines2228]

Gravity sort:

[@rian2013-eo5gq]

gravity sort: i'm faster

[@Fingeroo]

Marge Sort

[@SimonsAstronomy]

👌

[@Pacvalham]

However, quick's worst case is worse than merge's.

[@rredy]

Heap sort vs quicksort?

[@lucakun3455]

now do heap sort

[@caio757]

O(n log n)

[@the_irs_real]

bruh youtube keeps recommending ts to me 💀

[@pathpad3769]

How to get into google sir?

[@bacon_with_brussels_sprout]

Freakysort

[@TehNitro]

👏🏼

[@SuperTurtle0]

Gravity sort solos unfortunately

[@ddnava96]

Quicksort is quick

[@ERRORRubiksZeraBrand]

but merge sort is faster in worst case than quick sort

[@nitsuga_but_not_really]

I hate doing quicksort on paper; too many wrong answers.

[@NikolasDavies-d7c]

Why

[@lokeswaramanikantasomisett760]

Good

[@Z_053]

Wheres bogo sort

[@nizamettinboyabatl5868]

Bogosort faster

[@user-sh6hn9cl6f]

Coool

[@nathangoedeke694]

Quicksort is controversial bc the worst time is n^2, but the vast majority of the time its nlogn

[@lLenn2]

C'mon, you should know by now that the names don't mean anything.

[@gdplayer1035]

no sound 0/10

[@karcer822]

Gaysort :v

[@taskfailedsuccesfully738]

And here you can see that Quick Sort is faster, however there ain't no way you're programming that, so just use Merge Sort

[@Alguem387]

Ok maybe AI will replace you

[@taskfailedsuccesfully738]

@@Alguem387 Bold of you to assume I have a job /j

[@harshitvishwakarma2038]

gay sort

[@devanshurawat826]

So professionally, you work for google,
and non professionally also you work for google. (via RUclips) 😄

[@ramfik8322]

merge sort is soo gay

[@Eutropios]

? How can a sorting algorithm be "gay"?

[@Flovus]

@@Eutropios I think he means the rainbow patterns you see with MergeSort early on.