001    package de.hska.java.aufgaben.sortieren;
002    
003    
004    /**
005     * Nicht-rekursive Implementierung von Mergesort ohne den Laufzeitkeller
006     * nachzubauen.
007     * Es werden zuerst alle Paare benachbarter Elemente verschmolzen.
008     * Danach sind diese Paar aufsteigend sortiert.
009     * Nun werden diese verschmolzen. Dies wird wiederholt bis
010     * das ganze Feld sortiert ist. 
011     * Die Schrittweite verdoppelt sich immer.
012     * <pre>
013     * 7 4 6 3 1 2 8 5
014     * 4 7
015     *     3 6
016     *         1 2
017     *             5 8
018     * 4 7 3 6 1 2 5 8
019     * 3 4 6 7
020     *         1 2 5 8
021     * 3 4 6 7 1 2 5 8
022     * 1 2 3 4 5 6 7 8
023     * </pre>
024     * <p>
025     * Diese Art der Sortierung wird auch als <em>Direktes Mischen</em> (zweier Bänder) bezeichnet.
026     * Statt eines Feldes sind die beiden zu verschmelzenden Folgen auf zwei getrennten Bändern
027     * gegeben.
028     * </p>
029     * 
030     * <p>
031     *   <a href="http://www.home.hs-karlsruhe.de/~pach0003/informatik_1/aufgaben/sortieren.html#mergesort">Zurück zum Aufgabentext</a>
032     * </p>
033     * 
034     * @author Christian Pape
035     */
036    public class Mergesort implements Sortieren {
037    
038            private int [] b;
039            
040            /**
041             * Sortiert die Zahl in a aufsteigend mit Mergesort ohne Rekursion.
042             */
043            public void sortieren(int[] a) {
044                    b = new int[a.length];
045                    int i = 1; // Initiale Schrittweite
046                    
047                    while (i < a.length) {
048                       merge(a, i);
049                       i *= 2; // Schrittweite verdoppeln
050                    }
051            }
052            
053            
054            /**
055             * Verschmelzt a[i]...a[i+breite-1] mit a[i+breite]..a[i+2*breite-1]
056             * nach dem Reissverschlussprinzip  für
057             * i = 0, 2*breite, 4*breite, 6*breite usw.
058             */
059            private void merge(int [] a, int breite) {
060                    for (int links = 0; links < a.length; links += 2 * breite) {
061                            int mitte = links + breite - 1;
062                            int rechts = links + 2 * breite - 1;
063    
064                            if (rechts >= a.length) {
065                                    rechts = a.length - 1;
066                            }
067                            verschmelzen(a, links, mitte, rechts);
068                    }
069            }
070    
071            /**
072             * Verschmelzen der aufsteigend sortierten Breiche 
073             *  a[links]...a[mitte] mit a[mitte+1]..a[rechts]
074             * zu einer aufsteigend sortierten Folge
075             *  a[links] .. a[rechts].
076             */
077        private void verschmelzen(int[] a, int links, int mitte, int rechts) {
078            int l = links;
079            int r = mitte + 1;
080    
081            for (int i = links; i <= rechts; i++) {
082                if (r > rechts || (l <= mitte && a[l] <= a[r])) {
083                    b[i] = a[l++];
084                } else if (l > mitte || (r <= rechts && a[r] <= a[l])) {
085                    b[i] = a[r++];
086                }
087            }
088    
089            for (int i = links; i <= rechts; i++) {
090                a[i] = b[i];
091            }
092        }
093    }