Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.Comparator;
- public class MergeSort {
- private static final int CUTOFF = 7;
- static Comparable[] aux;
- static Comparator c;
- private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
- assert isSorted(a, lo, mid); // precondition: a[lo..mid] sorted
- assert isSorted(a, mid + 1, hi); // precondition: a[mid+1..hi] sorted
- for (int k = lo; k <= hi; k++)
- aux[k] = a[k];
- int i = lo, j = mid + 1;
- for (int k = lo; k <= hi; k++) {
- if (i > mid) a[k] = aux[j++];
- else if (j > hi) a[k] = aux[i++];
- else if (less(aux[j], aux[i])) a[k] = aux[j++];
- else a[k] = aux[i++];
- }
- assert isSorted(a, lo, hi); // postcondition: a[lo..hi] sorted
- }
- private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {
- if (hi <= lo) return;
- if (hi <= lo + CUTOFF - 1) InsertionSort.sort(a, lo, hi, c);
- else {
- int mid = lo + (hi - lo) / 2;
- sort(a, aux, lo, mid);
- sort(a, aux, mid + 1, hi);
- if (!less(a[mid + 1], a[mid])) return;
- merge(a, aux, lo, mid, hi);
- }
- }
- public static void sort(Comparable[] a, Comparator x) {
- c = x;
- aux = new Comparable[a.length];
- sort(a, aux, 0, a.length - 1);
- }
- private static boolean isSorted(Comparable[] a, int l, int m) {
- for (int i = l; i <= m; i++)
- if (less(a[i], a[i - 1])) return false;
- return true;
- }
- private static boolean less(Object v, Object w) {
- return c.compare(v, w) < 0;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement