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]); } }