Things you should know

If you took any computer science, you should know these things already.
You can skip anything under a header that you already know about.

Big-O, or how hard is it to do something?

It's difficult to talk about how hard a problem is in the abstract.
Mostly, I use Big-O notation when talking about it.
Big-O is simply a convenient shorthand for approximately how many steps are involved.
If you want to count to 100, then there are 100 steps.
If you want to count to N, then there are N steps.
In Big-O that's O(N).
O(N) is pronounced "Order N", or sometimes "On the order of N".

When sorting, there are usually only two Big-Os that come up;

• O(N²)
Which means the number of steps is the square of the number of elements in the list.
So a 32 element list takes approximately 1024 steps (32 × 32) to sort.
• O(N log N)
Which means the number of steps is the the number of elements in the list times the log₂ of the number of steps.
So a 32 element list takes approximately 160 steps (32 × 5) to sort.

Sorting is an O(N log N) problem

When I was in college I was told sorting was (at best) an O(N log N) problem. That seemed strange to me.
I mean, sure, the best sorting algorithm known was O(N log N), but that's quite a bit different from claiming that the best sorting algorithm possible is O(N log N).
So I asked; how do we know that sorting is O(N log N)?
No one around me knew the answer. (This was before Google and Wikipedia)
When I finally found someone who (claimed they) knew the answer, they couldn't explain it to me in a way I could understand.
So here's my explanation of why sorting is O(N log N).

The existence of Merge sort proves that we can sort anything in O(N log N) - that's an upper limit.
For a lower limit, we need to use a little information theory.
A list can exist in N! states.
(We can pick N values for the first element, N-1 for the second, N-2 for the third and so on.)
Sorting involves comparing two values, and possibly moving them based on the result.
At best, we can have twice as many states of the partially sorted list after each step. (2^N)
We must continue doing steps until 2^steps is greater than N!.
In other words, the lower limit on steps needed is log₂(N!), rounded up.
In Big-O, log₂(N!) is O(N log N)

That last bit is because N! is less than N^N, but not by much.
log(N^N) = N × log N, and in Big-O the difference doesn't count, so O(N log N).

What's an Invariant?

When talking about sorting, some people use the term "invariant"
Invariant is just a shorter way of saying "the comparison function we use to sort with".
In these examples, I always sort from low to high but you could sort high to low, alphabetically, or any other way you like.
But you don't change the sort order in the middle.