Is it OK not to sort transactions at all? According to Mastering Bitcoin. Mining - Transaction Age, Fees, and Priority, miners sort transactions, using special parameter, called priority, which looks like

Priority = Sum (Value of input * Input Age) / Transaction Size

If the priority is greater than 57,600,000, it means that transaction is high priority and it will be written in the first 50 kb.

The question is: Is priority really necessary? I mean, if I'm a miner and I have e.g. 1000 unconfirmed transactions, is it ok to randomly choose 100 transactions and put them into the block just as it is? Without sorting by priority or fees?

Will it work out or I'll get reject message or something?
As long as all selected transactions are valid, you may select any transactions you want.

You should check that there are no double spends among the selected transactions and that you keep any transactions which build on each other in the correct order, i.e. if TX B spends an output of TX A, TX B has to be listed after TX A in the block if you select both.

Sorting them by fee rate (i.e. fee paid per data size or satoshi per byte) will greedily maximize the transaction fees that you collect per block, to optimize block usage while maximizing fee, you'd have to perhaps use a knapsack solver.

Priority was turned off by default in Bitcoin Core 0.12.0, I actually asked a few months ago whether any miners still select by priority.