User:Deo Favente

From Wikipedia, the free encyclopedia

GPL MergeSort in Java!

[edit] Merge Sort

        public static void sort(Object[] a) {
                sort(a, 0, a.length, null);
        }

        public static void sort(Object[] a, Comparator c) {
                sort(a, 0, a.length, c);
        }

        public static void sort(Object[] a, int fromIndex, int toIndex) {
                sort(a, fromIndex, toIndex, null);
        }

        public static void sort(Object[] a, int fromIndex, int toIndex, Comparator c) {
                if (fromIndex > toIndex)
                        throw new IllegalArgumentException("fromIndex " + fromIndex
                                        + " > toIndex " + toIndex);
                if (fromIndex < 0)
                        throw new ArrayIndexOutOfBoundsException();
                for (int chunk = fromIndex; chunk < toIndex; chunk += 6) {
                        int end = Math.min(chunk + 6, toIndex);
                        for (int i = chunk + 1; i < end; i++) {
                                if (Collections.compare(a[i - 1], a[i], c) > 0) {
                                        int j = i;
                                        Object elem = a[j];
                                        do {
                                                a[j] = a[j - 1];
                                                j--;
                                        } while (j > chunk
                                                        && Collections.compare(a[j - 1], elem, c) > 0);
                                        a[j] = elem;
                                }
                        }
                }
                int len = toIndex - fromIndex;
                if (len <= 6)
                        return;
                Object[] src = a;
                Object[] dest = new Object[len];
                Object[] t = null;
                int srcDestDiff = -fromIndex;
                for (int size = 6; size < len; size <<= 1) {
                        for (int start = fromIndex; start < toIndex; start += size << 1) {
                                int mid = start + size;
                                int end = Math.min(toIndex, mid + size);
                                if (mid >= end
                                                || Collections.compare(src[mid - 1], src[mid], c) <= 0) {
                                        System.arraycopy(src, start, dest, start + srcDestDiff, end
                                                        - start);
                                } else if (Collections.compare(src[start], src[end - 1], c) > 0) {
                                        System.arraycopy(src, start, dest,
                                                        end - size + srcDestDiff, size);
                                        System.arraycopy(src, mid, dest, start + srcDestDiff, end
                                                        - mid);
                                } else {
                                        int p1 = start;
                                        int p2 = mid;
                                        int i = start + srcDestDiff;

                                        while (p1 < mid && p2 < end) {
                                                dest[i++] = src[(Collections.compare(src[p1], src[p2],
                                                                c) <= 0 ? p1++ : p2++)];
                                        }
                                        if (p1 < mid)
                                                System.arraycopy(src, p1, dest, i, mid - p1);
                                        else
                                                System.arraycopy(src, p2, dest, i, end - p2);
                                }
                        }
                        t = src;
                        src = dest;
                        dest = t;
                        fromIndex += srcDestDiff;
                        toIndex += srcDestDiff;
                        srcDestDiff = -srcDestDiff;
                }
                if (src != a) {
                        System.arraycopy(src, 0, a, srcDestDiff, toIndex);
                }
        }

[edit] List overload methods

        public static void sort(List<Object> l) {
                sort(l, null);
        }

        public static void sort(List<Object> l, Comparator c) {
                Object[] a = l.toArray();
                sort(a, c);
                ListIterator i = l.listIterator();
                for (int pos = 0, alen = a.length; pos < alen; pos++) {
                        i.next();
                        i.set(a[pos]);
                }
        }