Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- public class A24 {
- /**
- * @param args the command line arguments
- */
- public static void main(String[] args) {
- List<Integer> l = new ArrayList<Integer>();
- l.add(4);
- l.add(3);
- l.add(9);
- sort(l);
- System.out.print(l);
- }
- static public <T extends Comparable<T>> void sort(List<T> a) {
- sortR(a, 0, a.size()-1);
- }
- private static <T extends Comparable<T>> void sortR(List<T> a, int p, int r) {
- if (r <= p) {
- return;
- }
- int q = (r + p) / 2;
- sortR(a, p, q);
- sortR(a, q + 1, r);
- merge(a, p, q, r);
- }
- private static <T extends Comparable<T>> void merge(List<T> a, int p, int q, int r) {
- int p1 = p; //runs through left part
- int p2 = q + 1; //runs through right part
- int d = 0;
- List<T> temp = new ArrayList<T>((r - p) + 1);
- while (p1 <= q && p2 <= r) {
- if (a.get(p1).compareTo(a.get(p2)) <= 0) {
- temp.set(d++, a.get(p1++));
- } else {
- temp.set(d++, a.get(p2++));
- }
- }
- while (p1 <= q) {
- temp.set(d++, a.get(p1++));
- }
- while (p2 <= r) {
- temp.set(d++, a.get(p2++));
- }
- for (int i = 0; i <= r - p; i++) {
- a.set(p + 1, temp.get(i));
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement