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.
The merge is an inherently sequential process. Are you claiming that somehow you can merge two sorted arrays in parallel using fine-grained locks? How exactly?
Do you have any good ideas about how I can solve the seat booking example using Erlang's model of parallelism? There is a block of seats. I want to be able to handle seat bookings in parallel. The seats that people might want to book could be in large groups - as large as all of the seats.
If you use transactional memory with threads and mutable state, then all your booking processes can access the board state in parallel with ACI properties. Obviously, parallelism is still limited, as it always it, but as long as your booking processes are accessing different parts of the seat data structure, they can run in parallel. If they try to access the same part of the structure at the same time, all but one will be rolled back, but that one still gets through. Hopefully, they access different parts of the structure and sail through.
Your suggested Erlang program has no parallelism in it at all (for the isolated part of the seat booking of course), and will not scale to 2 cores, let alone the 64 cores I have in my machines at work.
How will your STM example behave if the computer managing the transactions suddenly has a massive hardware failure?
This gives place to parallelism as soon as you have more than one plane to contend resources for in your concurrent model, which is most likely the case in the real world.
If you have only one plane, then you likely won't need to scale.
In Erlang, the normal way to do this is to have a single actor handled that shared job. That then becomes a huge bottleneck, and with more cores it gets to be more and more of a bottleneck. This is Amdahl's law. This is where Erlang breaks. In a language with shared state (that includes Haskell or ML with mutable references) I can use very fine grained locks, or perhaps transactional memory, over this shared part of the problem, and continue to scale beyond what Erlang was capable of. Probably not near n-times for n cores, but much closer than what Erlang would allow.
Erlang's message passing creates bottlenecks! And then there's no way out. In shared state you can be nice and message passing, but then also have the power to use very fine grained locks or TM to break down those bottlenecks.