Soluzione

import java.util.Random;
 
class ListNode {
    int info;
    ListNode prev;
    ListNode next;
}
 
public class ListaCollegata {
    private ListNode first;
    private ListNode last;
 
    public ListaCollegata() {
        first=last=null;
    }
 
    public void inserisciInCoda(int info) {
        ListNode l=new ListNode();
        l.info=info;
        if(first==null) {
            l.prev=l.next=null;
            first=last=l;
        } else {
            l.prev=last;
            l.next=null;
            last.next=l;
            last=l;
        }
    }
 
    public String toString() {
        ListNode l=first;
        String s=new String();
        while(l!=null) {
            s=s+l.info;
            l=l.next;
            if(l!=null)
                s=s+", ";
        }
        return s;
    }
 
    private ListNode trovaMeta(ListNode i, ListNode f) {
        boolean pari=true;
        while(i!=f) {
            if(pari)
                i=i.next;
            else
                f=f.prev;
            pari = !pari;
        }
        return i;
    }
 
    private ListNode mergeSortRic(ListNode i, ListNode f) {
 
        if(i==f) {
            i.prev = i.next = null;
            return i;
        }
        else {
            //Passo divide
            ListNode m = trovaMeta(i, f);
            ListNode i1 = mergeSortRic(i, m.prev);
            ListNode i2 = mergeSortRic(m, f);
 
            //Passo impera (merge)
            if(i1.info < i2.info) {
                i=i1;
                i1=i1.next;
            }   else {
                i=i2;
                i2=i2.next;
            }
            i.prev=null;
 
            ListNode p=i;
            while(i1!=null || i2!=null) {
                if(i1!=null && i2!=null) {
                    if(i1.info < i2.info) {
                        p.next = i1;
                        i1.prev = p;
                        i1 = i1.next;
                    } else {
                        p.next = i2;
                        i2.prev = p;
                        i2 = i2.next;
                    }
                } else if(i1 != null) { // i1 != null && i2 == null
                    p.next = i1;
                    i1.prev = p;
                    i1 = i1.next;
                } else { //i1 == null && i2 != null
                    p.next = i2;
                    i2.prev = p;
                    i2 = i2.next;
                }
                p=p.next;
            }
            p.next=null;
            return i;
        }
    }
 
    public void mergeSort() {
        if(first!=null) {
            ListNode i=mergeSortRic(first, last);
            first=i;
            while(i.next!=null)
                i=i.next;
            last=i;
        }
    }
 
    public static void riempiLista(ListaCollegata l, int n) {
        Random r=new Random();
        for(int i=0; i<n; i++)
            l.inserisciInCoda(r.nextInt());
    }
 
    public static long getTime(int dimLista, int n) {
        long tot=0;
        int i;
        for(i=0; i<n; i++) {
            ListaCollegata l=new ListaCollegata();
            riempiLista(l, dimLista);
            long start=System.currentTimeMillis();
            l.mergeSort();
            tot += (System.currentTimeMillis() - start);
        }
        return tot;
    }
 
    public static void main(String[] args) {
        long i;
        for(i=10; i<10000000; i*=10) {
            double t=getTime((int)i, 100);
            System.out.println(i + "\t" + t + "\t" + t/(i*Math.log(i)) + "\t" + t/(i*i));
        }
    }
}