FASTEST sorting algorithm. Ever! O(N)

What is the fastest sorting algorithm known to man? We find out by attempting to find an O(n) time complexity sorting algorithm. Until now, the sorting research has found O(n*log(n)) to be the best.

We discuss concepts of time complexity, decision-making, and how the best algorithm is bounded by the permutation tree of an array. A final trick is used to reduce complexity to O(N)!

00:00 Introduction
00:19 Prerequisites
00:40 Sorting Algorithms Comparison
01:32 Building a Permutation Tree
04:35 Finding the best permutation
05:45 Time Complexity Analysis
07:21 Proof through Contradiction
08:08 Parallel Sorting!
09:25 Thank you!

System Design Video Course:

Along with video lectures, this course has architecture diagrams, capacity planning, API contracts, and evaluation tests. It's a complete package.

Sources:

#sorting #algorithm #sortingalgorithm

[mohitthorat]

You said to express a number we require atleast Log(n) operation. But we don't include this in the Time complexity analysis of bubbe sort, still it's completely is O(N square). Why? Shouldn't it be more than N square?

[souravkumarcode]

This is what clickbait looks like for computer science students.

[SongSoundGood]

There is a sorting algorithm working in O(n) called eliminationsort. You eliminate every element that is out of order. By the end, you have a sorted list.

[TonKcedua]

Actually, the Faith Sort's time complexity is O(1) - you just take the input array, put all your faith in it being already sorted, and return it. Worst case scenario whatever god you believe in takes care of the rest.

[MeFreeBee]

The trick to faster sorting is to always buy your data pre-sorted!

[tusharsingh]

pregnant woman: (hits blunt) it wont affect my child.
the child: let's use bubble sort.

[ubermensch]

Ever heard of Schrodinger's + Heisenberg's sort? 🤩

The array is already sorted as long
You don't look the array 😂

[tjoloi]

"O(n) is not possible"

Do you want to learn about our lord and savior Sleep Sort?

[bruhe]

Good content but bad clickbait ):
The fastest sorting algorithm should have been O(1): By pointing to an empty list.

An empty list is always sorted.

[SlimThrull]

Random Sort is able to do it in O(n). It just doesn't happen very often. ;)





C'mon, you know you deserved this comment for that title. :P

[Yash-_-]

youtube guy explaining fastest sort algo:
me simply using .sort() method in python : KODER!!!

[janhavisavla]

Thanks to your videos. You're one of the reasons I'm placed today, that too within 15 days since the inception of placement season in my college. I used to suck at coding, now I can safely say that I'm amongst the top 20 coders of my class(PS: my college(VJTI, Mumbai) has very good coders ) . I am placed in Accolite (which recruits only 60 engineers all over India, I was amongst the 6 people they chose out of 300 students in a pool campus process, went through 1 written coding round, 3 gruesome tech rounds and one HR round ). I went till the last round of Morgan Stanley (top 5, but they chose only 2 sadly) and your system design videos helped me a lot through the process.

Now I've started competitive programming and I'm enjoying it a lot.
From a person who didn't get a single internship last year, to being amongst the first students to be placed this year. You've inspired me.
Thank you!
Keep up the good work! :)

[LucidProgramming]

Hi Guarav. I really like your content, and this video is no exception. I understand the marketing realities present on YouTube force one to make "clickable" titles. I really don't want to see smart channels like the one you run devolve into the Buzzfeed of YouTube. Granted, this is a far cry from the typical clickbait, but I just don't find those tactics to be genuine.

I wouldn't take the time to comment on other channels employing these same tactics, I just feel like the quality of content you usually produce is above the clickbait tactics. Hope you take this as constructive criticism, and not as a personal attack.

[BikashKumar-pzhc]

I totally and absolutely love the creative treatment.
This video always brings up a smile.
What's more the explanation is clear to an non-computer science student like me.
Great work Gaurav Sen.

[nomads]

Nicely explained, but that God part is little confusing, instead of that it would be better to say,
1) Comparisons will be at-most height of your decision tree
2) no of leaf nodes of this tree would be n! i.e. no. of permutation possible
3) and h >= log(no. of leaf node)

[JAYPRAKASH-uyrg]

My senior who works at a MNC suggested me your channel for system design videos, and trust me if I am saying that this channel has great great content for budding fresher's.
A big fan of yours 🙌🏻

[arwahsapi]

Dozens of years of my life as a programmer, I mostly use Sort() method in almost C# collections. I never care how it works. You have explained the subject very well mate. Thanks

[abhishek-kapoor]

Correct me if i am wrong but asymptotic notation are for machine-independent algorithm analysis but in this video, we are talking about machine-specific analysis which should not be present by the asymptotic notation. 🙃🙃

[gopishivakrishna]

haha.. laughed at the start looking at so many YOU.. Simple and neat explanation... I've been watching your videos lately and guess what ? You have a Subscriber ;)

[apolishchuk]

counting sort is O(N)
if values range is bounded