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 u_{k} 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.

Floor k

People waiting

(indicated by floor

they want

to go to)

u_{k}

4

1

0

3

2

1

2

4

2

1

3

1

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:

Floor k

People waiting

(indicated by floor

they want

to go to)

u_{k}

4

1

0

3

2

1

2

4

2

1

3

1

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:

Floor k

People waiting

u_{k}

4

1

0

3

2

1

2

4,3

2

1

0

Notice that we have updated u_{k} to take account of the new arrangement of people.

As u_{2} 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:

Floor k

People waiting

u_{k}

4

1

0

3

2,4

1

2

3

1

1

0

As u_{3} 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.

Floor k

People waiting

u_{k}

4

1,4

0

3

2

0

2

3

1

1

0

As u_{4} 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.

Floor k

People waiting

u_{k}

4

4

0

3

2,1

0

2

3

1

1

0

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

Floor k

People waiting

u_{k}

4

4

0

3

2

0

2

3,1

1

1

0

At this point u_{k-1}=u_{1} 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.

Floor k

People waiting

u_{k}

4

4

0

3

2,3

0

2

1

0

1

0

At this point u_{k-1}=u_{2} 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.

Floor k

People waiting

u_{k}

4

4

0

3

3

0

2

1,2

0

1

0

A this point we have u_{k-1}=u_{1}=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.

Floor k

People waiting

u_{k}

4

4

0

3

3

0

2

2

0

1

1

0

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.