Time complexity is one thing, runtime is another thing. Out of all sorting algorithms, heapsort has the best time and space complexity - O(nlogn) and O(n) (it's an in-place algorithm, meaning we don't even need to create a new array). However, it's runtime is not as great as those of the merge sort and quick sort. Quick sort has the fastest average runtime, and even though its worst case behavior is dreadful (the worst case scenario is when the array is in a sorted or reverse sorted order), 1. It's highly unlikely that large arrays will be in sorted orde, 2. It can be optimized in my ways to avoid these worst-case scenarios, e.g. by combining it with other algorithms like insertion sort which is an ideal algorithm for sorted or nearly sorted lists. Also, it is proven that any algorithm that uses *comparisons* must have an O(nlogn) time complexity. However, that doesn't refer to algorithms that use other methods. Hence, potentially there might be a linear sorting algorithm, we just haven't found it.
At the risk of being annoyingly pedantic, I want to mention that the nlogn bound only applies to comparison-based sorting. Linear-time average-case sorting does exist, such as the radix sort.
Very interesting topic, in my opinion there's a lot of things to take in account when we talk about sorting algorithms like time, space complexity, if there's a divide & conquer approach which requires recursion, if we can use an algorithm efficient for a specific type of elements to compare, if the sorting algorithm uses comparisons or not... In any case it depends on what we are reaching 😂👍
You know, these sort of things are mostly academic I've found in my career. It's rare that you're put in a situation where you are sorting stuff in memory. I feel like there is too much focus on this stuff in algo exercises. Big-O notation is good to know though
I would add that using the built-in sort will give better performance over time since the implementation may change, like Java switching to TimSort from Merge sort. This is the power of abstraction on display and why libraries are preferred over writing from scratch.
Great video as usual! Concise and informative. Would love to see this one expanded by adding multithreading into the mix, and see what kind of speedups can be achieved (if any) based on input size (maybe a parallel bubble sort with 1M elements would've finished in reasonable time).
If I am unsure of what algorithm to use in larger projects, I tend to go for merge sort for 2 reasons. 1. Stable, even though you may not need a stable sorting algorithm, it grants opportunities in the future. 2. No need to worry about worst cases. You will have the same time complexity regardless on how the list is sorted. This means that your application will run smoothly, and it's much easier to test from a performance point of view.
Nice video. However it's unfair to compare merge sort and quick sort when the underlying data structure is array. I want to see how things turned out if the underlying data structure is linked list.
Can you post the code you used for the sorting algorithms for this video? I made my own tests comparing selection sort and merge sort and the merge sort ran faster in every test. tests included array of 1 int, array of 2 ints, array of 7 ints, and one array of 10,000 random ints. Merge was always faster. So Im guessing I did something wrong...
You forgot the absolute best sorting algorithm: radix sort, with a time complexity of O(n) It only catches up with quick sort and merge sort after like 1 million elements but is really the way to go for HUUUUUGE lists
what I like about this channel is the educational content. Most programming channels are about selling me courses (algo expert *cough cough8) or people flexing muscles telling about how successful they are, which is useless content to me.
Everyone knows the best sorting algorithm is bogosort. I mean does any other algorithm have a slight but non zero chance of using only ONE operation on ANY array?
Great content, very educational. Quick question: Were all the sorting algorithms applied on the same array of random numbers for a given input size, or were they random arrays for each sort algo?
53 large metal rakes @23 dollars a piece -> $1219 + 45 scythes @35 dollars each -> 1535 + 110 torches @ 5 dollars each -> $550 == $3344. Now I think it would be best if you also payed for lunch. We are assuming a group of around 100 rioters here so that could cost a couple thousand. Let's say after all expenses...... Just go ahead and pay me $7000. An I'll arrange the massacre.
You should make a video about Big O notation, because it's a topic that is hard to understand but important!
I have a video on it already
Why don't we worry about HeapSort? Is HeapSort ok? Someone check on them please! 😭
HeapSort is the most beautiful sorting algorithm in the world lololo
Heapsort is an in place n log n worst case algorithm. It really should have been in the test
Time complexity is one thing, runtime is another thing. Out of all sorting algorithms, heapsort has the best time and space complexity - O(nlogn) and O(n) (it's an in-place algorithm, meaning we don't even need to create a new array). However, it's runtime is not as great as those of the merge sort and quick sort.
Quick sort has the fastest average runtime, and even though its worst case behavior is dreadful (the worst case scenario is when the array is in a sorted or reverse sorted order), 1. It's highly unlikely that large arrays will be in sorted orde, 2. It can be optimized in my ways to avoid these worst-case scenarios, e.g. by combining it with other algorithms like insertion sort which is an ideal algorithm for sorted or nearly sorted lists.
Also, it is proven that any algorithm that uses *comparisons* must have an O(nlogn) time complexity. However, that doesn't refer to algorithms that use other methods. Hence, potentially there might be a linear sorting algorithm, we just haven't found it.
sort by most based to least based
Debase currency!
@@m.a.t.a.s yes
Very helpful video. I briefly learned about the Bubble Sort and Merge Sort I believe last semester in high school which was a long time ago.
Tbh I use the one I don't understand😂
array.sort((a, b) => a - b) ez pz
At the risk of being annoyingly pedantic, I want to mention that the nlogn bound only applies to comparison-based sorting. Linear-time average-case sorting does exist, such as the radix sort.
Obviously bogosort is the fastest.
Very interesting topic, in my opinion there's a lot of things to take in account when we talk about sorting algorithms like time, space complexity, if there's a divide & conquer approach which requires recursion, if we can use an algorithm efficient for a specific type of elements to compare, if the sorting algorithm uses comparisons or not...
In any case it depends on what we are reaching 😂👍
Yeah as someone who always tries to optimise for memory (embedded and mobile devices) I'd love to see a space complexity focused analysis 😁
Thank you for this! It would be great if you could do some videos about Spring Boot, I like how you explain stuff. ☺️🤩
You know, these sort of things are mostly academic I've found in my career. It's rare that you're put in a situation where you are sorting stuff in memory. I feel like there is too much focus on this stuff in algo exercises. Big-O notation is good to know though
Great video man! Cant believe how much I learnt about sorting algorithms in only 8 mins. Great job! love the videos!
bogo sort is the best sorting algorithm, it can sort in the first try
Very true. It could also sort on the 500 quadrillionth try.
I would add that using the built-in sort will give better performance over time since the implementation may change, like Java switching to TimSort from Merge sort. This is the power of abstraction on display and why libraries are preferred over writing from scratch.
Bogosort xD
Lol I got the same shirt from h&m
Technically sorting algorithm "by comparison" cannot be faster than nlgn. But algorithm that are not comparison-based can be faster than nlgn
this video is really casual. Not so interesting.
Idk why, but heap sort is my favorite sorting algorithm. Such an amazing video btw
Very nice video, love your explanation. Keep posting this tip of videos, or curses
BogoSort (unbounded). All day every day.
Best place to learn algorithms and data structures?
Great video as usual! Concise and informative.
Would love to see this one expanded by adding multithreading into the mix, and see what kind of speedups can be achieved (if any) based on input size (maybe a parallel bubble sort with 1M elements would've finished in reasonable time).
This is such a great idea! Would love to see that too 🙏
@@KaroCodes hello karo help me open up trading coding robot
pretty interesting video, thanks for the info
If I am unsure of what algorithm to use in larger projects, I tend to go for merge sort for 2 reasons. 1. Stable, even though you may not need a stable sorting algorithm, it grants opportunities in the future. 2. No need to worry about worst cases. You will have the same time complexity regardless on how the list is sorted. This means that your application will run smoothly, and it's much easier to test from a performance point of view.
Nice video. However it's unfair to compare merge sort and quick sort when the underlying data structure is array. I want to see how things turned out if the underlying data structure is linked list.
Can you post the code you used for the sorting algorithms for this video? I made my own tests comparing selection sort and merge sort and the merge sort ran faster in every test. tests included array of 1 int, array of 2 ints, array of 7 ints, and one array of 10,000 random ints. Merge was always faster. So Im guessing I did something wrong...
You forgot the absolute best sorting algorithm:
radix sort, with a time complexity of O(n)
It only catches up with quick sort and merge sort after like 1 million elements but is really the way to go for HUUUUUGE lists
what I like about this channel is the educational content. Most programming channels are about selling me courses (algo expert *cough cough8) or people flexing muscles telling about how successful they are, which is useless content to me.
Everyone knows the best sorting algorithm is bogosort. I mean does any other algorithm have a slight but non zero chance of using only ONE operation on ANY array?
Next could you explain the RUclips algorithm? It's giving me trouble.
RUclips algorithm
Great content, very educational. Quick question:
Were all the sorting algorithms applied on the same array of random numbers for a given input size, or were they random arrays for each sort algo?
Spend all that time learning this, and then get into web develop and haven't used it in the last 9 years....
A bit disappointing that you did not mention warmup cycles when measuring the performance.
Talk about github Co pilot
Hello help me on coding
first?
maybe?
Depends on which sort algorithm you use.
@@Vennotius nice one XD
good video
is best case time complexity of quick sort not n?
Thanks dude you made it simple and clear.
Bogosort ftw
Now do it in HTML
Now kill me please, I can afford all the masacre tools JUST DO IT
53 large metal rakes @23 dollars a piece -> $1219 + 45 scythes @35 dollars each -> 1535 + 110 torches @ 5 dollars each -> $550 == $3344.
Now I think it would be best if you also payed for lunch. We are assuming a group of around 100 rioters here so that could cost a couple thousand. Let's say after all expenses...... Just go ahead and pay me $7000. An I'll arrange the massacre.
Highly knowledgeable
nice video!