まじで

Sandbox.java

package net.firsp.sandbox;

import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Sandbox {
    public static <T> List<T> mergeList(List<T> a, List<T> b, Comparator<? super T> cmp) {
        List<T> m = new ArrayList(a.size() + b.size());
        int ap = 0;
        int bp = 0;
        while(true){
            if (a.size() == ap) {
                m.addAll(b.subList(bp, b.size()));
                return m;
            }
            if (b.size() == bp) {
                m.addAll(a.subList(ap, a.size()));
                return m;
            }
            if (cmp.compare(a.get(ap), b.get(bp)) < 0) {
                m.add(a.get(ap));
                ap += 1;
            } else {
                m.add(b.get(bp));
                bp += 1;
            }
        }
    }

    public static <T> List<T> mergeSort(List<T> list, Comparator<? super T> cmp){
        //don't execute if smaller
        if(list.size() < 2) return list;
        int len = list.size() >> 1; // equation list.size() / 2
        //divide into two parts
        return mergeList(mergeSort(list.subList(0, len), cmp), mergeSort(list.subList(len, list.size()), cmp), cmp);
    }

    public static void main(String... args){
        List<Integer> i = IntStream.range(0, 10000).boxed().collect(Collectors.toList());
        Collections.shuffle(i);
        System.out.println(mergeSort(i, (a,b) -> a < b ? -1 : 1));
    }
}

まじです