Imagine you’re the cool kid at school. Yes, I know it’s hard, but close your eyes and give it a try. As the cool kid you’re responsible for a handful of things:

• Acting cool;
• Telling yo’ mama jokes;
• Keeping your hair wet it’s 2015, you no longer need that!

You’re also responsible for picking who gets to be on your basketball team during recess.

You don’t really hate geek kids, but you don’t love them either. Just a couple of days ago one of them tried to teach you something about a way of sorting stuff. It was probably called selection sort, but you can’t really recall. Probably it had something to do with natural selection, or whatever.

But I'm already wandering. Focus… Focus... What really matters right now is that you need to pick the best players for your team.

Who Are the Best Players

Everyone's seated at the bench, waiting to be picked by you. After all they might have the privilege of playing with the cool kid. Yes, that's you!

Now that you think of it, they're seated in no particular order. There are tall kids, next to skinny kids. There’s a group of kids that don’t even look interested in playing. They seem more interested in their pokémons. And then there’s a couple of other kids with different skill levels.

You’ve been watching some of them play during the last recess. You don’t want to look bad in front of the other kids, so you took some mental notes on the skills of each kid. People don’t realize how hard it is, to make it all seem cool and without effort, right?

So you give each kid a score from -10 to 10 according to their skills:

• -10: the pokémon kids that are not even remotely interested in playing. If you choose them, they might end up helping the opposite team just to piss you off;
• 0: the kids that have no basketball skills whatsoever;
• 10: the kids that will score you points and make you look good.

Pick the Next Best Player, One at a Time

This is the easy part. You already know how to pick your team:

• Pick the next best player available from the bench;
• Ask them to to sit on your team's bench.

Arg... You forgot how this school really sucks! The other bench is across the field. If you ask kids to go sit on that bench, you'll spend the whole recess building your team. All this would have been for nothing. You wouldn’t have any time left to play.

There has to be another way. Maybe... Just maybe...

Ask Players to Switch Places on the Bench

Some crazy idea goes through your mind. You decide to try this:

• You start at the beginning of the bench;
• You call the best player to your right, and ask them to switch places with the kid in front of you.

If you do this for every seat, it might actually work. You're a genius! As you keep moving to the right, the players to your left end up seated by their skills.

And so you give it a try.

#1 - The Next Best is on Your Right. Don't Settle!

You start at the first seat of the bench. You look at all the kids seated to your right. The kid in front of you is pretty good, but might not be the best. So you just continue looking all the way to the end of the bench.

"Still no better than the one in front of me. Nah. More interested in pokémons, nop, nop, nop. Kind of better, but still nop. Nah, nah. WOW!"

You're glad you didn't stick with that first kid. Right at the end of the bench is the best player of the whole school. How lucky!

"Common, hurry up and switch places. We don't have all day!" - You say, pointing to the kid in front of you and the best player.

#2 - Step to Your Right and Repeat, Repeat, Repeat, ...

So you step one seat to your right. You're a genius! Like you had predicted, the players to your left will be seated in the order of their skill.

In your head you're humming "1,2. If you're the second best, I'm coming for you..."

As expected. You find the second best and ask to swap with the kid in front of you.

#3 - Never Trust Your Luck

Again you move a seat to the right.

You've learned your lesson with the first kids. It payed off to look all the way until the end of the bench. The one at the very end was the best player. So there are no exceptions! Even though the kid in front of you seems to have great skills, you still need to double check all the way until the end of the bench. You just never know!

Yup. Just by chance it happened, and the next best was already in front of you. But you just never know.

Another crazy idea goes through your mind.

"If you switch the kid on the 3rd seat with herself she would end up in the same place... Wow, what? Switch someone with themselves? That's some crazy talk right there!"

You focus and continue moving to your right. One seat at a time.

...and 10! - You've Got the Best Team

After some moving to the right, and making kids switch places a couple of times, they're seated according to their skills.

So Powerful You Could Even Pick the Worst Team

Just as expected... You can't concentrate for two minutes without having some crazy idea going through your head. This time you're thinking:

"What if I did the exact same thing, but instead of choosing the next best I chose the next worst? What might have happened?"

Then you shake your head. That would leave kids seated from worst to best. Unless you'd want to build the worst team ever, that would be useless.

Recess is Over. Your Dreams are Crushed

Whaaaat? The bell's already ringing? How can that be? You're already late for the next class.

You take off running to the class. When crossing the door Mr. Sed asks you why you're late. Again.

You explain that this time you were trying to create the best basketball team ever. You even found a way to do just that. He seems intrigued, and asks how you plan on doing that.

"It's easy Mr Sed! You pick the best, and faaaaaha... Forget about that. I'll line up all the kids in the school. Then I stand in front of the first kid. I check who's the next best player to my right and ask them to switch places with the kid in front of me. If I continue moving to my right one place at a time, the kids end up positioned by their skills."

Mr Sed looks back at you. You can't read his poker face. Maybe he's thinking about kicking you out of the class for being late. Or probably he has ignored everything you just said.

After what looks like an eternity he says in a non-judgemental voice:

"No wonder you're late! What you just described is called Selection Sort. It works nicely but is kind of slow."

Mr Sed sighs. He usually does that before trying to think of the best way to explain something.

It's kind of slow because you need to compare each kid with all the kids to your right. So if you have 10 kids:

• You'll need to compare the 1st kid with the other 9;
• You'll need to compare the 2nd kid with the other 8;
• You'll need to compare the 3nd kid with the other 7;
• And so on.

You're kind of lost trying to understand what he's saying. So you close your eyes just a bit, trying to focus all your attention. And that's when it hits you.

Wow! Yes Mr Sed, you're right! So what?

Well... What if instead of 10 kids, you had to find the best players from the whole school? And for the whole city? And for the whole country?

Again you close your eyes a bit. You try to image the number of kids growing, and growing, and growing. Now there are so many that's getting difficult to imagine.

OMG! That's Too Much Work

Yes Mr Sed, so what?

You see, at first you might think that adding one or two more kids to your list of players wouldn't be much more work for you. After all it's just or or two more. Our school has 100 kids. So I bet that if a new kid arrived and asked to be part of your draft, you wouldn't really mind, would you? But oh boy, you'd be in for a ton of work!

Just look! By just adding one extra kid, you'd have to do not one, not two, but 101 extra comparisons! That's some serious work right there! You'd have to compare each of the 100 kids with the new one.

Can you imagine... This single speck giving you all that work?

And we're only talking about our school. Now imagine that for the whole city. And the whole country! It would be even worse. You'd have to compare a new student with the rest of the students in the country!

Christ, That's a Lot of Time

Now you're not sure if Mr Sed is just trying to freak you out. But he continues...

Lets say that it takes you one second to compare two kids. You need to have a good look a them, so one second doesn't seem much. Now, if there are:

• 10 kids, you'd take around one minute;
• 100 kids, or the whole school, would take you almost an hour and a half;
• A city like Mountain View, would take you almost a year and a half;
• A county like Santa Clara, would take you almost 2500 years!

Now you're thinking - Wow, 2500 years! Probably not even those vampires from the Twilight saga would be alive by then. Thank god!

Mr Sed notices you're distracted, so he asks - Can you guess how long would it take if all the kids in California wanted to be part of your draft? Lets say California has around 9 million kids.

You look to Mr Sed, without knowing what to think. Probably he's just bullshiting you. No way he has a formula to calculate how much time it takes to sort out 9 million kids.

So you try guessing

"ONE MILLION YEARS"

Mr Sed looks back at you. He seems surprised. Then he asks - Did you really figure that out, or you just tried out your luck?

You're not sure if you're right or not, so you think it's best to admit it - Yes, I just made that up.

A Triangle is Just Half a Square. Really?

Have you noticed that independently of how many kids we are talking about, the number of comparisons always looks like a square? - Mr Sed says.

This means that if you have N kids, you'll have to compare NxN...

You're a bit confused, and cut Mr Sed right when he was going to continue. NxN comparisons? But the kids to my left are already seated in the right order. I don't need to compare them with any other kid, right?

Mr Sed, how's that NxN comparisons? When I'm halfway through the bench, I don't need to look to the kids to my left. They are already seated by their skill. I only need to compare the kid in front of me with the ones on my right.

If you just let me finish - Sighs Mr Sed. Yes, the kids to your left are already on their correct seat. You only need to compare the kid in front of you with the ones to your right. To seat all the kids you'll need NxN/2 comparisons.

And you jockingly say - Yes! Half a square of comparisons. Or better yet, a full triangle!

Mr Sed looks at you in a funny way. He asks again - So can you now tell me how long you'd take if 9 million kids participated in your draft?

You start thinking. NxN/2... So that's 9 million x 9 million / 2. That's a bunch of seconds, but if I transform that to years... Uh, uhuh, sounds about right. That should take me around... yes 1.2 Million years!

Mr Sed smiles and says - now lets stop all this nonsense. We need to get this class started.