Ich glaube, wir müssen das wirklich nochmal von Anfang an erklären und besser visualisieren.
Stellt Euch mal ein Regal vor. Ein solches hat eine endliche Anzahl an Fächern. Wir nehmen an, dass in jedes Fach genau ein Gegenstand passt und dass alle Fächer nebeneinander liegen. Die Kapazität des Regals ist endlich und entspricht genau der Anzahl der Fächer. Außerdem nummerieren wir die Fächer durch von links nach rechts, beginnend bei 0.
Zusätzlich nehmen wir an, dass an jedem Fach ein sich automatisch schließendes Türchen (wir haben ja bald Advent) angebracht ist. D. h. um zu sehen, was sich in einem Fach befindet, muss man erst das Türchen öffnen.
Auf jedem Gegenstand im Regal befinde sich ein Preiszettel und wir gehen jetzt erstmal davon aus, dass das Regal vollständig gefüllt ist.
Frage: wie findet man den Gegenstand mit dem höchsten Preis?
Variante #1: man sieht sich den Preis des Gegenstands im ersten Fach an. Wir merken uns, dass das der bislang höchste Preis ist und dieser im Fach 0 gefunden wurde. Jetzt öffnet man ein Türchen nach dem anderen und vergleicht den Preis des Gegenstands im jeweiligen Fach mit dem gemerkten, bislang höchsten Preis. Wurde ein höherer Preis gefunden, ersetzt dieser den bislang höchsten Preis und wir merken uns wieder, in welchem Fach dieser gefunden wurde. Ist kein Türchen mehr übrig, ist der bislang höchste Preis auch der höchste Preis und wir wissen, in welchem Fach sich der teuerste Gegenstand befindet.
Variante #2: Wir beginnen wieder beim ersten Fach. Wir vergleichen den Preis mit dem des Gegenstands, der sich hinter dem nächsten Fach befindet. Ist der Gegenstand im linken Fach teurer als der im rechten Fach, vertauschen wir die Gegenstände. Das wiederholt man nun für jedes Fach mit Ausnahme des letzten (da es dann kein nächstes Fach mehr gibt). Hat man das einmal durch, befindet sich der teuerste Gegenstand im letzten Fach.
Frage: wie erreicht man mit Variante #1 auch, dass sich der teuerste Gegenstand im letzten Fach befindet?
Naja, wir wissen ja, hinter welchem Fach sich der teuerste Gegenstand verbirgt. Folglich brauchen wir nur den Gegenstände dieses Fachs mit dem Gegenstand im letzten Fach zu tauschen.
_________________
So, an dieser Stelle ein Einschub. Wir stellen uns wieder ein Regal vor. Jetzt wollen wir aber nichts finden sondern Gegenstände hinzufügen. Um uns die Sache zu vereinfachen, nehmen wir an, dass ein Regel immer von links aus lückenlos befüllt wird.
Frage: woher weiß man, in welches Fach der neue Gegenstand gelegt werden muss?
Da das Regal immer von links aus und immer lückenlos gefüllt werden soll, ist das trivial: man schreibt sich auf, wie viele Gegenstände man schon ins Regal gelegt hat.
Frage: wie fügt man also einen Gegenstand dem Regal hinzu?
Nun, wenn im Regal x Gegenstände liegen, dann ist das Fach x das nächste leere. D. h. wir legen in Fach x den Gegenstand und auf unserem Zettel erhöhen wir das x um eins. Natürlich funktioniert das nur, so lange noch Platz ist.
_________________
Zurück zum Thema: wir haben nun unser gefülltes Regal von oben und wissen, in welchem Fach sich der teuerste Gegenstand befindet. Jetzt bauen wir ein zweites Regal, das höchstens ein Fach weniger besitzt als das erste (mehr darf es ruhig haben).
Frage: wie überträgt man nun alle Gegenstände - mit Ausnahme des teuersten - in das zweite Regal?
Wenn der Gegenstand sich im letzten Fach befindet, ist das trivial: wir beginnen beim ersten Fach, nehmen den Gegenstand heraus und fügen ihn dem zweiten Regal hinzu (s. o.) Dann folgt das nächste Fach usw. Das machen wir so lange wir noch nicht das letzte Fach des ersten Regals erreicht haben, da sich dort der teuerste Gegenstand befindet, der nicht übertragen werden soll.
Befindet sich der Gegenstand nicht im letzten Fach, funktioniert das ganz analog, muss aber bei jedem Fach prüfen, ob es sich nicht um das Fach mit dem teuersten Gegenstand handelt. In diesem Fall wird das Fach einfach ausgelassen. Die Übertragung ist vollständig abgeschlossen, wenn alle Fächer (inkl. des letzten) behandelt wurden.
Frage: wie funktioniert es, wenn es mehrere "ursprüngliche Regale" gibt? (Zweidimensionaler Fall)
Das könnt Ihr Euch anhand des Regals selbst überlegen.