Let's just try it, all our n integers in a row, 1, 2, and so on, n.

Below them let's write the same set of integers, but in the reverse order.

So, n, then n minus 1, and so on, 2, and 1.

Then what we get is a row of size 2 by n.

Having n columns, and in each column,

the sum of the corresponding two integers is equal to n plus 1.

Great, so in the first column we have n and one, and in the second column we have

two and minus one and so on and in the last column we have n and one.

So the sum in each column is equal to n plus one and zero n columns.

Which means that the sum of all the numbers in our table is equal to n,

when supplied by n plus one.

So since this table contains our sum, the sum of the integers from 1 to n twice,

we conclude that the sum of all the numbers from 1 to n is equal to n(n+1)/2.

Another possibility to find this formula, to see why this formula is correct

is to take a rectangle of size n, of dimensions n multiplied by n plus 1.

So it's area is equal to n multiplied by n plus one.

And to cut it into two parts such as it's shown in the slide,

such as the area of each of these two parts is equal to 1 + 2 + and so on n.

We're all ready to conclude.

So we've just discussed the selection sort algorithm.

This algorithm is easy to implement, easy to analyze, and

it's running time is n squared, where n is the size of the input sequence.

So it sorts the input sequence and array in place.

Meaning that it requires almost no extra memory.

I mean, all extra memory which is required by this algorithm is only for

storing indices, like i, j and m index.

There are many other quadratic algorithms, like insertion sort and bubble sort.

We're not going to cover them here, and instead,

in the next video we will proceed, to do a faster, a faster sort algorithm.