<p>There is a very nice article by Bachmat, Berend, Sapir, Skiena and Stolyarov entitled <a href="http://arxiv.org/abs/physics/0512020" rel="nofollow">Analysis of airplane boarding via space-time geometry and random matrix theory</a> that models this exact problem for airplane boarding. From their abstract:</p>

<blockquote>
  <p>We show that airplane boarding can be
  asymptotically modeled by
  2-dimensional Lorentzian geometry.
  Boarding time is given by the maximal
  proper time among curves in the model.
  Discrepancies between the model and
  simulation results are closely related
  to random matrix theory. We then show
  how such models can be used to explain
  why some commonly practiced airline
  boarding policies are ineffective and
  even detrimental.</p>
</blockquote>

<p>The conclusions of the paper are:</p>

<ul>
<li>BEST: Window-Middle-Aisle</li>
<li>NEAR OPTIMAL: Random Boarding </li>
<li>REALLY BAD: Back-to-Front</li>
</ul>

<p>For your set-up, I think this means you should ignore <strong>how far down the aisle</strong> the people are and instead focus on <strong>how far from the aisle</strong> they are. This model also accounts for time to store luggage, so you may need to adjust that somewhat for your situation. In any event, I think this confirms what you are finding through your model.</p>
What's the best reserved seat sorting algorithm?
<p>I'm trying to find the best algorithm for the following sorting problem.</p>

<p>There are <strong>N = K × M</strong> seats in an auditorium with one aisle, <strong>K</strong> rows, and <strong>M</strong> seats per aisle. The assumption is made that <strong>K</strong> is a bigger than <strong>M</strong>, but I don't think that's very important. There are <strong>N</strong> people that are in
bijection with the seats (assigned seats). Assuming that people don't
like waiting, what's the fastest way to line them up to get them all
in their seats as quickly as possible?</p>

<p>I ran some simple experiements (using random permutations) and it
seemed that letting them line up randomly is faster than having the
people in the front third (further down the aisle) line up first, then
the middle third, then the back third. That seems wrong to me. </p>

<p>I'm writing this in MatLab if that matters at all. Any ideas or answers?</p>