Dear XQC

All right, so this video is for XQC. If you're not XQC, stop watching this video. All right, Mr. QC, I saw you watching some sorting algorithms. I'd always knew you were a bit of a computer science boy. You know, they always say computer science is the third highest skill ceiling, second being Overwatch, first one being Rocket League. Now, I'm somewhat of a computer scientist myself. And while watching that video of you looking at sorting algorithms, I realized you got a little bit of misinformation, but you also got a couple things really correct. First, let's actually talk about the thing you got right. Wait, how? That's slow. That is so bad. Okay, so what you were looking at is insertion sort. Insertion sort is bad, but the reason why it's bad, you kind of guessed to the whole scanning of the arrow. So, how does insertion sort work? Well, it's actually pretty simple. Imagine you have a big list of numbers. Let's just say 2, 8, and one for right now. If you run insertion sort, it starts on the first one. Well, if there's only a list of one number, it's always sorted. So, how it works is it takes eight and it will walk backwards until it hits a number smaller than eight. Well, right away, first check, two smaller than eight. Okay, these two are sorted. Then it gets to one. Now, one does the exact same thing. Is one smaller than eight? It is. Okay, that means we have to swap eight for one. Is one smaller than two? Yes, it is. We need to swap one for two. And now our new list is going to be 1 28. You can even see in the video that the height of the lines have to go all the way back into the position over and over and over again. One element at a time, DUDE. SEE, I TOLD YOU MERGE SWORDS FASTER. WA WA WA WA wa wa. First off, that's some misinformation right there. Okay, somebody's been bamboozingly. Whoever created that quick sort algorithm, they failed you. They lied to your face, my friend. Before I show you why quicksort is in fact faster than merge sort and how they actually work. First, here's the code for quicksort right here. Okay, a little bit of C, you know, the Lord's language. And here's the code for merge sort also in C, the Lord's language. I made the script actually run a quick sort and merge sort on 1,000 long list of numbers 1,000 times. And quicksort, it does it almost every single time at 35 34 milliseconds, whereas merge sort does it about 50 milliseconds, 51 milliseconds. So, whoever made that merge sort implementation and that quicksort implementation, they're just not good programmers, okay? They probably just generated the code with chat jippity just did it all wrong. Chat jippity. All right, so how does merge sort work? Well, first off, you can imagine you have a really long list of numbers right here. You split that list in twain. Let's pretend we had 1,024 numbers. The next list, we have two sets of 512 numbers. If we split it again, we'll have four lists of 256. If you keep splitting it in twain, you will eventually get to lists of size one. So the reason why it's called merge sort is right here. We get a bunch of these one-sized arrays and now we have to combine them. So we're going to take two one-sized array. Let's say the other side is eight. And we're going to say, okay, let's combine these in order. That means we're going to first want to take the smaller one and then we take the bigger one. So we have one and eight. Now we're going to have a whole bunch of size two arrays. Now we're going to combine them each into size four arrays. So, let's pretend we have another one that has two and seven. Well, then what were we going to do? We're going to combine it. Okay, we're going to take the one from this side. That's a one. Then we're going to take this one from this side. That's a two. Then we take the seven from this side. And then we're going to take the eight. And now we have an array of size four. And then you keep doing this all the way back up. In other words, we have to look through every single one of the one sized arrays once. Meaning, we have to walk the array one time or size n or 1024 in this case. Then we have to walk through all of the size 2 arrays one time. Another n then 4 8 16 32 64 128 256 and 512. And after you've done all of that, that means you've walked the size of n log n times. Or in other words, we have a running time of n login. NOW THIS IS PRETTY FAST. OKAY, this is pretty dang fast. The thing that makes merge sort slower is that when you create say the list of two from two ones, you have to create a brand new list and then move each number up into it. When you create a list of four, you have to move each number up into it. So you have to keep on creating a bunch of memory, a bunch of sublists and eventually you have to create n log n amount of memory. So this is typically why merge sort is just slower. Even if you are a novice in the old computer science realm, you can see right away this is much better than insertion sort because insertion sort you could have to walk the entire length of the array over and over and over again. And my gosh, did you see that? I just freehand two completely straight lines and then just like a little crook just like a little bit of one. But quicksort's different because you take the same array and you just pick a random element out of the array. And then you put all the things that are smaller than this one that you picked on this side and all the things that are larger on this side. And this one singular element is actually sorted. The rest is not sorted. And then you take this longer list and this shorter list and you do the exact same thing. You pick a random number and then you put all the smaller elements on one side, all the larger elements on the other side. But here's the trick. Notice that you don't have to create new arrays to reconstruct it. Instead, you actually sort in place, meaning you don't create a bunch of memory. You want to hear something weird, though? Quicksort often uses insertion sort as the lists get really, really small. So if you have a list of four items left, instead of doing another quick sort list of splitting the list, then calling itself again, then splitting it again down to one, and then regoing back up the tree, instead all it does it goes, okay, well, I can just sort this list with insertion sort because it's actually much faster than calling functions cuz it turns out swapping just a few indices is actually blazingly fast. So is insertion sort slow? Yes, it is slow. But is it always slow? No. No, it's not. Anyways, I thought I'd just give you a little quick tip on the old algorithms, okay? The old sorting algorithms. Hey, if you ever need one explained, next time I'll get out the whiteboard, okay? Hey, you want dystras? I'll get you dystras, buddy. The name is the primogen. Hey, do you want to learn how to code? Do you want to become a better back-end engineer? Well, you got to check out boot.dev. Now, I personally have made a couple courses from them. I have live walkthroughs free available on YouTube of the whole course. Everything on boot.dev Dev, you can go through for free. But if you want the gamified experience, the tracking of your learning and all that, then you got to pay up the money. But hey, go check them out. It's awesome. Many content creators you know and you like make courses there. boot.dev/prime for 25% off.