Verfahren

Ein Feld wird in drei Teile geteilt. Das mittlere Teilfeld muß mindestens so groß, wie das linke und rechte Teilfeld sein. Zum Sortieren wird nun das linke und mittlere, dann das mittlere und rechte und dannach wieder das linke und mittlere Teilfeld sortiert. In den jeweiligen Teilfeldern wird genauso verfahren. Spätestens bei einem zweielementigen Teilfeld muß bei Bedarf eine Vertauschung stattfinden. Wird das alles beachtet, dann haben wir irgendwann ein vollständig sortiertes Feld.