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

The inspiration for this code was this github repo

I used this algorithm to turn a wavelength into an RGB color

Thumbnail Background image (Thunderstorm) by FelixMittermeier

[aojntm]

Oh hell yeah finally YouTube is recommending me good shit

[xTriplexS]

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

[marble]

> I bet on Merge Sort
> I lost my money

[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.

[theolinder]

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

[moveonvillain]

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.

[Aloyzn]

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

[alyx]

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

[santitabnavascues]

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.

[acasualviewer]

unlike mergesort, quicksort isn't stable

unlike quicksort, mergesort requires o(n) additional storage to work

[HelloUser]

Really helpful comparison, thank you!

[justussneary]

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

[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.

[doomse]

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.

[Abstract_zx]

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

[nathangoedeke]

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

[hillstrong]

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

[donovanmahan]

"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"

[hobocraft]

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