In-Place LSD Radix Sort

[@Musicombo]

Visit our community Discord here: discord.com/invite/2xGkKC2 Check out the NEW home for ArrayV here: github.com/gaming32/ArrayV-v4.0

[@edwardclark6731]

A small seizure warning for this channel Algorithm sorts can be extremely loud, and seizures can be triggered by noises Algorithm sorts can flash a lot, and seizures can be triggered by flashing Be careful, and have a good stay!

[@ERRORRubiksZeraBrand]

H O W D O I D O W N L O A D I T

[@RashaMaya123]

Do Double Binary Insertion Sort Reverse Selection Sort Stable Selection Sort Stable Cycle Sort Tree Sort (AA Balanced) Wiggle Sort Optimized Bubble Sort Unoptimized Bubble Sort Swapless Bubble Sort Sample sort Weaved Merge Sort Iterative Merge Sort Stable Merge Sort Radix LSD Sort Base 2 Optimized Cycle Sort

[@ERRORRubiksZeraBrand]

@@RashaMaya123 DOES ANYONE KNOW HOW TO DOWNLOAD IT

[@RashaMaya123]

@@ERRORRubiksZeraBrand YES

[@KeaveMind]

Radix is by far my favorite Sort. The absolutely Alien sounds, the way it seems to scroll across the screen, the chaos that suddenly turns into satisfying patterns. Just gorgeous

[@duothehybrid]

The first video of this sort is one of my favorite, the absolute power of the echo at the end

[@Tarou9000]

the scrolling of the screen is an effect of In-place LSD Radix Sort, not Radix Sort

[@nhungduong3236]

Same but in place or out of place as I want

[@bitonic589]

​@@nhungduong3236You like inefficient sorting algorithms which literally defeat the whole purpose of a sort?

[@45_689]

never thought it'd be so satisfying seeing the swaps counter finally hit 10 million at some point, lol

[@shanshansan]

9:34 for the 10 million swaps

[@adrianodemetrio5607]

Oh god it was so satisfying, I read this comment at the start of the video and checked every counter until the 10 million, it was always so close it hurted

[@ABCDEFG-mw6wu]

i thought i was the only one

[@phantomtroopyt]

So satisfying 😭

[@bobczech7774]

Imagine it says 9,999,999 😂😢

[@azurbtkl3901]

I love those "TA DI DI DA DA DI DI DA DA" parts when the small peaks come all together after the big figures

[@gallium-gonzollium]

Me when searching a song I don’t remember the name of:

[@KatzRool]

lmao

[@edwardclark6731]

I like the OUUUUUUUUUUUUUUUUUUEEEEEEOOOOOOOOOEOEOEOEOEOEOEOEOEOEOEOEOEO at the end and the DUDUDUDUDUUUDUDUDUDUDUDUDUDUDUDUDUDDUDUDUDUDDUDUDUDUDUDDUDUDUUDD at the beggning

[@DeveloperJake]

“TA DI DI DA DA DI DI DA DA” I feel like now would be a good time for us to tell you that there are no voice tones on the internet

[@Ghal00xx]

I also like radix sort but merge sorte is best for me

[@LazyTheoRenders]

0:19 listen closely and you can hear the THX intro

[@smo_cuberunners]

but perfectly cutoff

[@jaypaint4855]

Sounds really cool, and the LSD naming is hilarious PS I have a newfound obsession with sorting algorithms, especially these radix LSD ones

[@edwardclark6731]

lsd stands for least significant digit, and this sort is sorta inneficient, however there are cool and efficent sorts like american flag sort

[@idiotgame1026]

Same

[@edwardclark6731]

And yes its absolutely hilarious it's named LSD sort -it fits-

[@dna_rosepetal_wcue]

ok, *nerd*. i wonder who this **nerd** is.@@edwardclark6731

[@theplayer12312]

LSD Radixsort has gotta be my favourite sort, just because how rugged it is, you can just about throw anything at it and it'll sort it in a respectable amount of time, and every sort takes a almost fixed amount of time, even on the in-place version, and the pre-final pass being sorted is just so satisfying to watch and hear, even if you throw the most bonkers list at it

[@bitonic589]

its ass try sorting [1, 2, 34859295492942, 8] with lsd radix sort it'll take long asf but insertion sort will do it instantly

[@theplayer12312]

@@bitonic589 In what real world application would you put LSD Radix through a 4 digit array with wildly different values?

[@soosboi]

​​@@bitonic589but here's the thing, insertion takes longer than than Radix LSD in huge arrays,which is why i think double insertion sort should be more used.

[@kydatyvegrybatokeanvisoko2420]

idk why im so obsessed with sorting algorithms especially cuz ik what basis most of them are going by to sort things but 5:15 i like this one it sparks joy

[@LittleFarmLife2024]

00:05:30🍓

[@417Owsy]

Radix Base 10 sort be like: 1. Check entire thing 2. blblblblblblblbl 3. done

[@nhungduong3236]

The orders you said are correct! Congratulations! Here's a billion dollars!

[@kingcatthethird]

1. Scan 2. EAUOHEBEAEBOEHAOEHO 3. blblblblblblblblblblblblblblblbl 4. errrrrrrrooooooiiiiiii

[@TheOne_6]

your average radix in-place LSD base 10 consists of: -efficiency -sounding like an alien in a microwave -broken music disc

[@DeveloperJake]

I like when it starts the Shepard tone for a minute

[@letter_o_hyphen_letter_o]

love that running radix start to finish on "radix final pass" creates a sort of shepard tone on the second(?) pass

[@Plaston_]

Theses frequances sweeps are quite good at stressing speakers, it help them softing their suspensions and test their bandwidth.

[@jonnelk.pabico5402]

1:46 えええええーぅううううううあおあううううう！！！！！

[@frzferdinand72]

1:45 It sounds like music from Portal

[@Somaiscariot]

Who else really misses dubstep? 💕

[@distendedmist5840]

I love it it is like a cheque printer chucking out stuff

[@HamStar_]

the fan favorite

[@nameisChannelID]

This is what everyone comes for

[@majman446]

This is my favorite sort - and the weirdest one for sure. It's so weird that bro literally made a whole video dedicated to it.

[@AndrewChumKaser]

To explain what this sort is doing technically, it's actually startlingly simple: Take the value of the last digit of the element's number and sort them by it. (So for example if something's value is 1485, 5 is its what it sorts by). This digit is called the least significant digit, where the algorithm gets its name from. (LSD) Anyway, next do the same sort for the next digit to the left of each element in each category, or the next least significant digit of the element. Then do the same thing again for the next LSD, (repeating this for each and every number of digits in all the values, in this case four) then the final digit, or the most significant digit (MSD). Doing this will sort the list by its value. The reason why this works is because it's a stable sort: the elements are arranged in sorted form and stay that way between steps within their "categories" often called buckets, of the previous step. That's also why it "sounds" like it's raising in pitch in the final step, because if you think of it in terms of each bucket they're already sorted.

[@BryndanMeyerholtTheRealDeal]

This, but with a million numbers. I wonder how fast it will be?

[@mewity]

computer crash moment

[@costa-w3k]

I wonder how SLOW* would it be We are talking about Radix sort, man

[@TechSY730]

​@@costa-w3k _in-place_ radix sort is what is really slow. If you allow for auxiliary data structures (like a helper array), then radix sort becomes one of the best around, with O(n) runtime.

[@AndrewChumKaser]

Radix has a lot of overheads but it's also linear: it actually gets better in terms of efficiency compared to other algorithms with a lot of elements. Radix doesn't have to deal with an exponentially larger and larger number of comparisons to make as the elements increase, because it just checks the value of each one a number of times equal to its digits (in base 4 so each one has the same number of them). Other algorithms slow down a lot from so many elements to compare, but radix actually handles them like a champ because it essentially doesn't do any true "comparisons".

[@jsmcfadyen]

I thought in-place meant no writes to auxiliary arrays

[@Musicombo]

Nope, doesn't have to be that strict! There's a bit of leeway with the definition. Some would argue a sort that doesn't use O(n) extra space can be considered in-place. Note that this doesn't have to be in terms of just arrays! Quicksort uses O(log n) stack space, yet it's universally considered in-place.

[@mahinwahid5161]

Musicombo I like your funny words magic man

[@Musicombo]

Lol, thank you? 😅

[@smaybius]

The aux space is just for the buckets and determining them. The items in the array are never moved out of place

[@RashaMaya123]

​@@Musicombo Do Over 300 Sorting Algorithms In Under An Hour Reversed Inputs

[@ishu4227]

what i think radix does is it scans the thing, and repeatedley slices the pieces into 10 little pieces, and i guess this happens so much it gets sorted.

[@hoodiedude4204]

LSD means least signifikant digit. It sorts the array based on only the ones place, then it sorts THAT array based on the tens place and then it sorts it based on the hundreds place and so on. Its always only the ones, tens and hundreds etc places that is considered, not the entire numbers, hence the comparisons counter stays at 0

[@DFPercush]

Creel has a good video explaining radix sort : /watch?v=_KhZ7F-jOlI

[@DonnaDinaMusic]

у меня в глазах рябит от этого но я не могу оторваться

[@ProTheRobloxer]

Me: What’s 1+1? My brain: 0:06 My brain: “3”

[@LittleFarmLife2024]

I think 00:07:33 is kinda Creeepy (For Me) Broken Machine! 404 040 440 004 444 000 044 400

[@twostepverification590]

I can't believe the whole sorting board moved in a single frame

[@neurotoxic1830]

Oh my god it sometimes sounds like peeling off tape from the roll but continuous

[@maxvangulik1988]

Imagine if someone made bad apple in this software

[@ryoukaip]

lmao its quita hard tho edit: *quite

[@mewity]

badapplesort

[@nhungduong3236]

It's logically impossible

[@maxvangulik1988]

@@nhungduong3236 could approximate it

[@rosanafalcao4038]

5:28 First one to sound different 6:01 First one to sound *almost completely* different

[@LazyTheoRenders]

0:31 what was the point in that

[@CSDragon]

moving on to the next sort, which was "what happens if the array is sorted backwards" sort

[@Matheus_Braz]

@@CSDragon how does this even work though, even if its all mixed up, repeating it enough times somehow brings it back to normal?

[@CSDragon]

@@Matheus_Braz it's actually showing the worst possible case when it's completely backwards like that.

[@Matheus_Braz]

@@CSDragon yeah but how does repeating it, even when its backwards, just magically bring it back to normal??

[@edwardclark6731]

@@Matheus_Braz here, so basically, it takes it, (i presume) and it makes it into groups, and keeps on dividing it into small pieces, and then grouping them into order, leaving a small grey bit, which is added onto the base, thus sorting it! i hope i helped! tl;dr: it divides alot, then makes it triangle with grey, added to white.

[@陳娟娟-t6f]

Radix LSD Sort In-Place Base-10 Cool, Like 1. Random 2. Reversed 3. Almost Sorted 4. Many Similar 5. Scrambled Tail 6. Scrambled Head 7. Final Merge Pass 8. Sawtooth Input 9. Final Merge Reversed Array 10. Reversed Final Merge 11. Pipe Organ 12. Final Radix Pass 13. Final Pairwise Pass 14. Binary Search Tree 15. Heapified Input 16. Smooth Input 17. Poplar Input 18. Half-Reverse Input 19. Even Reverse Odd In-Order 20. Even In-Order Odds 21. Even Ascend, Odd Desascend 22. Bell Curve 23. Perlin Noise Curve 24. Perlin Curve 25. Triangular Input Done

[@陳娟娟-t6f]

In-Place LSD Radixsort (Base-10): Reverse Sort

[@LittleFarmLife2024]

Everything is same, Except 00:05:30!

[@demirbey8068]

Oh its the "Why so quiet?" *3 seconds later* "Oh, thats why" guy.

[@Ceafto2007]

Radix sort base 2? Or base 1?

[@Ceafto2007]

@Nehemiah Britt no, I mean, how would base one and base two work?

[@signisot5264]

@@Ceafto2007 Base 2 would work similar to base 10 but with 2 buckets instead of 10 (Likely takes more combovers), but I'm not sure if there's a base 1 edition

[@HamStar_]

base 1: it moves everything into the same bucket each time, but in a different order equivalent to bogosort

[@signisot5264]

@@HamStar_ lol bogo

[@Ceafto2007]

Could be an interesting video

[@Terpster77]

RADIX

[@LSCrazyCabCo]

but is there such thing as an unsorting algorithm?

[@edwardclark6731]

Bogosort

[@ericcartman80085]

shuffle

[@My1xT]

yeah this looks so trippy this algo HAS TO have taken some drugs

[@MissyStarofficialchannel]

00:05:30❤️‍🔥❤️‍🔥❤️‍🔥

[@Button_Pushing]

How does this algorithm work?

[@UmbralKnight1344]

This sorting algorithm works by looking at a certain digit of every data point each pass, going from smallest to largets (i.e. 1s place, then 10s place, then 100s place, etc.) and sorting them in to n (n being the base used, such as base 10 in this video) "buckets" based on the digit it looks at. once it goes through all the digits, the array is sorted.

[@edwardclark6731]

use like base two or base 5894

[@itryen7632]

WHERE'S THE VOLUME >:(

[@Musicombo]

...Huh?

[@peace.divinity]

@@Musicombo every radix lsd has loud sound...

[@Musicombo]

Yes... and?

[@Anopeng]

After these videos I realized that I have sortophobia...

[@hydrate6913]

i change my mind.

[@idiotgame1026]

9:34

[@LittleFarmLife2024]

Bill...IGuess

[@uncreativename957]

The sound when my computer is not computering

[@serg_sel7526]

Basically it stabilly sorts every number by first digit, then second, then third, then fourth and etc... Sadly, it can sort only digits...

[@hollyhello8352]

no idea how it works, but its so cool!!!

[@smaybius]

In normal LSD radix, the array is loaded into buckets of the values of the lowest digit, then unloaded back to the array, then rinse and repeat for the next digit up

[@Fera-gr5mm]

@@smaybius Technically the bucket part is implementation detail, you just need to known how to sort the items by n-th digit

[@hiatus0017]

what app is this?

[@sbuydi_sweeddat]

Start Redix from Final Redix then stop at Final Redix and repeat

[@keanjuguetaphkinemastertv4885]

All Musicombo Sorting Videos

[@itryen7632]

This is looking like one of those Japanese music videos now

[@Newvik2Bsystem]

LSB Radixsort in Embrassed No waveinvert mono only

[@badboycorolla86]

cool video, i always want that app on my computer

[@52markin]

Seems like the thx intro

[@itryen7632]

FUCK YEAH SORT IT ROOOIGHHT

[@Questiala124]

10:00 10 million at 10 minutes for the 10^0th time!

[@minhluat-6789]

Xin Chúc Mừng Bạn Nhận Được 10.000.000 Người Đăng Ký

[@Arufi000]

this is what lsd feels like

[@S1LLYSC3N3C0R3LARA]

7:20 my brain at school:

[@andysetiawanart7669]

Don't base 10, should be base 16 in radix LSD Sort in place

[@aeezem]

watch this on lsd

[@andysetiawanart7669]

Seharusnya base 16 jangan 10, kalau pilih 10 kurang sempurna lihatnya

[@xirex4705]

but what is update.

[@TheDudeThatDoesNothing]

0:51 THX Intro

[@daisyreeabalde7888]

25 Ways to In-place LSD Radixsort Base-10

[@Buckybadgerwisco]

this is just base 10

[@Indrakrn]

Sounds like lagging ps2 games

[@ert5419]

WHAT

[@Caterblock]

Another one

[@leyasep5919]

Funny but inefficient 😕

[@tgb2024]

krnl sort 4.0

[@ethanramcel2749]

Fast

[@ethanramcel2749]

Slow

[@edwardclark6731]

525 ms. ITS SLOW

[@lephihung10]

/tp 65.50 68.56 65.50

[@chrisrodriguezm13]

This isn’t Minecraft

[@liondyi]

it’s called LSD for a reason