001    /*
002     * Created on 10.12.2004
003     *
004     * $Log:$
005     *
006     */
007    package de.hska.info1.uebung.sortieren;
008    
009    import de.hska.info1.sortieren.Sortieren;
010    
011    /**
012     * Implementiert Sortierten durch Verschmelzen (Mergesort).
013     * 
014     * @author Christian Pape
015     */
016    public class MergeSort implements Sortieren {
017    
018        private int [] b;
019    
020        /**
021         * Sortieren mit Mergesort.
022         */
023        public void mergesort(int[] a) {
024            b = new int[a.length];
025            mergesort(a, 0, a.length - 1);
026        }
027    
028        /**
029         * Rekursive Implementierung von Mergesort. Zeitaufwand ist O(n log n).
030         * Zusätzlicher Speicheraufwand ist O(n).
031         * 
032         * @param a
033         *            das zu sortierende Feld, darf nicht null sein
034         * @param links
035         *            die linke, untere Grenze, ab der die Zahlen in a sortiert
036         *            werden sollen
037         * @param rechts
038         *            die rechte, obere Grenze, bis zu der die Zahlen
039         *            einschliesslich sortiert werden sollen
040         */
041        private void mergesort(int[] a, int links, int rechts) {
042            if (links < rechts) {
043                int mitte = (links + rechts) / 2;
044                mergesort(a, links, mitte);
045                mergesort(a, mitte + 1, rechts);
046                reisverschluss(a, links, mitte, rechts);
047            }
048        }
049    
050        /**
051         * Verschmelzt zwei aufsteigend sortierte Folgen a[links] bis a[mitte] und
052         * a[mitte+1] bis a[rechts] zu einer aufsteigend sortierten Folge genau
053         * dieser Zahlen. Die sortierte Folge ist danach in a[links] bis a[rechts]
054         * enthalten. Zeit- und Speicheraufwand ist O(n).
055         * 
056         * @param a
057         *            Feld, dass die beiden zu verschmelzenden aufsteigend
058         *            sortierten Folgen enthält.
059         * @param links
060         *            Index erste Zahl, der ersten sortierten Folge
061         * @param mitte
062         *            Index letzte Zahl, der ersten sortierten Folge. mitte+1 ist
063         *            Index der ersten Zahl, der zweiten sortierten Folge
064         * @param rechts
065         *            Index der letzten Zahl, der zweiten sortierten Folge.
066         */
067        private void reisverschluss(int[] a, int links, int mitte, int rechts) {
068            int l = links;
069            int r = mitte + 1;
070    
071            for (int i = links; i <= rechts; i++) {
072                if (r > rechts || (l <= mitte && a[l] <= a[r])) {
073                    b[i] = a[l++];
074                } else if (l > mitte || (r <= rechts && a[r] <= a[l])) {
075                    b[i] = a[r++];
076                }
077            }
078    
079            // kopierte sortierte Folge b nach a
080            for (int i = links; i <= rechts; i++) {
081                a[i] = b[i];
082            }
083        }
084    
085            public void sortieren(int[] a) {
086                    mergesort(a);
087            }
088    }