Order by column should have index or not?

Actually - for some millions rows better to apply some well thought out index, it is not so big dataset for beginning to worry about space-performance issues.

but

If you read that table once a day and update/delete rows 100 times per second - then effect from the index may degrade performance of main operations, while occasinally selecting will perform better.

So, the answer as usual - it depends

It is depends on your query. MySQL can use a composite index for both where clause and order by . It is If you include an ORDER BY clause explicitly that contains the same column list, MySQL optimizes it away without any speed penalty, although the sorting still occurs. If a query includes GROUP BY but you want to avoid the overhead of sorting the result, you can suppress sorting by specifying ORDER BY NULL.

More details

http://download.nust.na/pub6/mysql/doc/refman/5.1/en/order-by-optimization.html

If you are not good at MySQL optimization better to use some good tools like SmartMySQL which can identify best indexes for your queries based on table structure and it's data. It is free GUI tool which can optimize query and speed up your development 10 times faster compare to MySQL's Workbench.

You can download it from www.smartmysql.com

Order by columns are used for ordering the result set, not filtering. An index on the columns mentioned in the order by clause is unlikely to change anything, especially if it's not used to filter the data.