Here are some ideas for your two problems.
First, the problem is sorting. One very efficient algorithm is to utilize a parallel sampling sort algorithm. The idea is to start off P processes and sampling randomly to obtain P-1 splitting elements. Then the Array of P-1 splitters are distributed to each of the P processes and input data is now sent around so each processor has its batch of data. Next, each process sorts its own batch. It turns out to be pretty fast in practice to run this kind of operation and it may be fast enough.
Note the distinct advantage of message passing here: It works, even if a process is running on another physical machine - shared memory doesn't. Also note that Erlang is not really built for parallel computation, and your example is one. My guess is that you can achieve a pretty good speedup with a sampling sort variant on multiple cores.
As for your flight seat problem, it really isn't. Keep the state of a plane in a process. That is have a single process assigning seats in the plane. On very large planes you may have 500-1000 seats. Hardly something which will dwarf a single process. Chances are, however, that you may want to assign seats to multiple planes at the same time. In that case you get your concurrency and a possible speedup.
As for getting linear speedup in Erlang systems:
First, your problem must expose the necessary amount of work. That is, there must always be something to do for an idle processor. In Erlang, this is easy to achieve if there are multiple agents interacting with the system at the same time, or you can create it yourself by spawning off some processes for each incoming job.
Second, your program must avoid contention around a single process. That is, you must ensure processors are not all looking for the same resource. We have tools like percept, the lock counter and dtrace for that.
An Erlang process works very much like transactional memory if written correctly. But TM has the same problem: contend around a resource and you are in trouble. It might be that the breaking point for contention is different due to different characteristics in overhead, but in principle the contention problem is also there.
Finally, there is a "cheating" possibility. Erlang provides ETS which is a tuple space for erlang terms. It allows parallel read and write access outside the process context. And very fast such RW access. For certain problems it can be used to allow multiple processes read access to the same data which can in turn speed their work up considerably.
But ETS is not distributed, oh the horror! Enter mnesia, which distributes ETS over multiple machines and optionally provides persistence. Mnesia is really a memcached/redis distributed in memory key/value store with DB-like query properties. Limited - but oh so powerful for certain problems.