ANSWER

Knuth, Donald, The Art Of Computer Programming. Vol 3, pp 357-360.”One tape sorting”.

You can also look up Karp's algorithm.

The key to the algorithm is not to treat the people already in the elevator as any different to the people waiting for the lift.

The algorithm works with an up and a down mode of operation.

You also need to keep track of the number of people wanting to move higher than a given floor and those wanting to move lower. This is a complicated piece of book-keeping but it is what makes the algorithm work, so we can't avoid it.

On each floor k you need to count u_k the number of people on that floor and below it who want to go higher than that floor.

So if there is one person on each floor wanting to go to the floors as indicated, then uk for floor 3 is 1 because on floor 3 and below there is only one person wanting to go higher than floor 3.  For floor 2 u_k is 2 because there are two people wanting to go higher than floor 2 who are on floor 2 or below.

You can see the other values for u_k in the table. 

Up

The basic idea is to start in the lobby and fill the car with passengers with the highest possible destination floor - as the car is finite some might not get on.

Move up one floor i.e. k=k+1.

Drop off all the passengers off the next floor up to create a combined pool of passengers waiting for the elevator. (They don't all have to get out as long as the passengers to the next floor are picked from the combined group so as to be traveling to the highest floors.)

Adjust the values of u_k  based the total passengers on the floor and in the lift.

As long as u_k>0 keep going up.

Allow passengers with the highest possible destination floor to get onto the elevator and move to floor k+1

Yes some passengers have had to get out a the wrong floor - but as Knuth says "This represents their sacrifice for the common good".

Down

If there are no passengers on the floor or below wanting to go higher then we switch to the down-moving mode.

Treating all of the passengers on the floor and in the lift as a single pool, let on the passengers who want to go to the lowest floors.

Move down to floor k-1 and adjust or recompute the values of u_k based the total passengers on the floor and in the lift.

As long as u_k-1>0 keep going down - notice that is the floor below's value that is tested.

If u_k-1=0 and u_k=0 keep going down  - otherwise switch to going up.

Repeat until everyone is where they want to be.

You should be able to see that this algorithm corresponds to picking at each floor the passengers who want to travel the maximum distance in the current direction - irrespective of whether they are already on the lift or not. The really clever bit is working out when to change direction of travel based on the total number of people who want to move up at or below the floor.

This is is Karp's algorithm and it is proved to be the way to get everyone to the right floor in the minimum total time.

The simplest case to illustrate the algorithm is if  there is one person per floor and the elevator car only holds one person.

Suppose we start with:

Where the numbers in the people waiting column shows which floor the people want to be on. The first up phase takes the person wanting to go to floor 3 and moves up to floor 2 - where they all get out to produce:

Notice that we have updated u_k to take account of the new arrangement of people.

As u₂ is non-zero we keep moving up.

Now the passenger that wants to go to the highest floor is floor 4. This means the passenger who got on at floor 1 is left behind on the wrong floor. This gives:

As u₃ is non-zero we keep moving up.

In this case the passenger riding to the fourth floor stays in the lift and makes it to their floor at the next step.

As u₄ is zero we switch to moving down.

We now select passengers wanting to go to the lowest floors hence the passenger wanting to go to floor 1 gets in.

Notice that at this point we don't switch back to going up because u_k-1=u₂ is non-zero. Thus, the person wanting to move to floor 1 moves to floor 2.

At this point u_k-1=u₁ is zero so we switch to the going up mode and the person wanting to go to floor 3 gets in the lift which takes them to floor 3.
 

At this point u_k-1=u₂ is zero so we switch to the going down mode and the person wanting to go to floor 2 gets in the lift which takes them to floor 2.

 A this point we have u_k-1=u₁=0 and you might think that we need to switch direction, but as u_k=0 we continue moving down. You can see that this extra condition is needed to complete the move.  

One last move down delivers the final person to the correct floor.

And with this the job is done.

Of course to see the algorithm really work you need to have more floors, more people and a bigger car. But the idea of getting everyone out at each floor and then picking the ones going the maximum distance in either the up or down direction is the key to the algorithm.

• Joe Celko is best known as the database expert who writes  books on SQL, data and databases. But before that, he was an honest developer obsessed with finding good algorithms and clean code.

The Disaster Team Puzzle