Skip to content

Instantly share code, notes, and snippets.

@firstspring1845
Created July 18, 2015 16:38
Show Gist options
  • Save firstspring1845/9ab4cb1a64e64784935e to your computer and use it in GitHub Desktop.
Save firstspring1845/9ab4cb1a64e64784935e to your computer and use it in GitHub Desktop.
まじで
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));
}
}
@firstspring1845
Copy link
Author

まじです

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment