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.