SQL is inherently unordered.
How does ClickHouse behave on that matter? Can we expect same query to return rows in same order in the consequent executions? Does it depend on table engine, like ENGINE = Memory()? If so please elaborate on possible engine scenarios affecting order.
In case the order results is not guaranteed what is the cheapest way to achieve it? ORDER BY primary/sorted key?
The answer is no: ClickHouse does not return data in deterministic order unless you ask for it.
More broadly you should not make any assumptions about default ordering of data in ClickHouse result sets. The MergeTree table engine family (which is the workhorse engine for large datasets) organizes data in 'parts' and runs queries in parallel across them even on single nodes. By default it returns the results from each part as they emerge from query processing. Data within the parts will typically return in the sort order from the table but the results from each part can return in any order.
You should therefore apply a sort if you care about the ordering. The most efficient sort is the order already enforced by the CREATE TABLE ORDER BY clause. If you need radically different orders just ask for them in the query. If they then turn out to be slow (which can be the case if you have very different query patterns over the same data) you can optimize the results by adding a materialized view to sort data into a better order for particular queries.
For more general questions on this topic check out the ClickHouse docs especially https://clickhouse.com/docs/engines/table-engines/mergetree-family/mergetree. I also did a ClickHouse talk a couple days ago on looking into the exact issue of why result sets look they way they do. Slides are here: https://www.slideshare.net/Altinity/dangerous-on-clickhouse-in-30-minutes-by-robert-hodges-altinity-ceo