Merge sort for a List<T>

Your temp array is static, this immediately makes your function not thread-safe and non-reentrant. Instead add it to the parameter list.

1. Binary operators should always be surrounded by whitespaces(it is inconsistent in your code: sometimes you do surround them, sometimes you don't). For example,

   for (int j=0; j<a.length; j++)
   

   should be

   for (int j = 0; j < a.length; j++)
   

2. There should be one whitespace before an opening bracket. Again, there is an inconsistency in your code: a whitspace is present most of the time, but it is not present, for instance, here: if(hi <= lo){. Not following established style guidelines is not good, having inconsistencies is definitely bad.

3. A little bit about blank lines: they should be present between different methods and it is fine to have them inside one method if it is really big and you need to separate logical blocks from each other(however, too long methods should be avoided). But having a blank line after each statement is pointless and it makes your code less readable.

   private static void sort(Object[] a, int lo, int hi) {
       if(hi <= lo) {
           return;
       }
       int mid = lo + (hi - lo) / 2;
       sort(a, lo, mid); // sort left part
       sort(a, mid + 1, hi); // sort right part
       merge(a, lo, mid, hi);
   }
   

   looks better than:

   private static void sort(Object[] a, int lo, int hi) {
   
       if(hi <= lo){
   
           return;
   
       }
   
       int mid = lo + (hi - lo)/2;
   
       sort(a, lo, mid);// sort left part
   
       sort(a, mid+1, hi); // sort right part
   
       merge(a, lo, mid, hi);
   
   }
   

4. Variable naming. There is no need to shorten words: you code will become more readable if you use names like low and high instead of lo and hi.

5. It is conventional to declare one variable at a time. I would use

   int i = lo;
   int j = mid + 1;
   

   instead of int i = lo, j = mid+1;. And again, i and j are not the best names for variables because they are not descriptive(but it can be ok if their scope is very narrow, so it is not a very big issue in this case).

6. It is a good practice to write comments for each public method to describe what it does, what do its parameters stand for, what pre- and post-conditions are guaranteed, what exceptions can be thrown, is it thread-safe or not and so in. You should write comments for all public classes, too.

In addition to the great answers you already got, I'd suggest using braces in the if-cascade, so you have a clear separation of tested conditions and their respective statements.

This makes that code easier to read and extend and most of all less error prone. Suppose you want to add another conditional action in your merge method, right next to the

else if (j > hi ) a[k] = temp[i++];

so that in addition to the assigment, something like this is also done (e.g. logging):

if(someCondition) do("stuff");

It would go horribly wrong if you forgot to add braces since the next else would not be tied to its original if anymore.

Variable naming

It seems that you're trying to shorten your variables too much: Object[] a, ListIterator<T> i, int lo, int hi, etc. are not fantastic. It takes more effort for the reader to understand these names as they're used.

Instead you could use something like Object[] objArr, ListIterator<T> listIter, int low, int high, etc. Those are a lot easier to follow.

I would definitely avoid naming anything just i, because i, j, k are almost always used in loops (as you've done yourself!), so using i to name a ListIterator<T> is not a good idea, primarily because it's misleading due to the conventional uses of i.

Well, algorithmically the code is rather absurd. You copy arrays in the recursion. The first thing to note is that a mergesort is fundamentally a list sorting operation not requiring any copying. Copying to an array at all makes only sense when you hope to exploit the better memory locality of array access. That, in turn, only makes sense when you do not use indirection when sorting but rather swap the underlying data directly. Which only makes sense for small data types.

So there are a lot of ifs and buts that mean it is easier to just work on lists directly. With regard to the List data type it is worth noting that you can get a considerable faster sort by violating the list invariances of doubly linked lists, sorting only the forward pointing list in O(n lg n) operations and then do a single pass through the result in order to reconstitute the backward list.

However, that means that your sorting is better done as part of the List implementation than as something using List as a blackbox.

If you take a list of typical recursive mergesort implementations, it is worth noting that they tend to skip half of the given list in order to arrive at the second sublist. Since skipping half of the given list is done anyway when sorting the first sublist, by letting the sort return the head of the second sublist one saves this only-skipping pass as well.

I seem to remember that the Linux kernel source has a pretty good list mergesort implementation (of course in C rather than C++) that basically only suffers from not hardcoding small lists which would save some O(n) amount from the overall O(n lg n) complexity. For comparatively small lists, this can make a noticeable difference.

The Linux kernel version also sorts sublists generally of size 2^k which has the advantage that one does not need to know the list length in advance (which is needed for splitting some n into almost equally sized parts), at the cost of about O(n) extra comparisons in the worst case.

Note that I am not at all talking about your C++ style: this critique is exclusively about the running time and memory requirements of the compiled code. I consider it a mistake to not consider this a part of the quality assesment of code.

A few more points in addition to what others have already said.

Use foreach when you can

This for loop can be replaced with foreach:

    for (int j = 0; j < a.length; j++) {
        i.next();
        i.set((T) a[j]);
    }

Like this:

    for (Object item : a) {
        i.next();
        i.set((T) item);
    }

Simplify method signature

You can simplify this declaration:

public static <T extends Comparable<? super T>> void sort(List<T> array){

Like this:

public static <T extends Comparable<T>> void sort(List<T> list) {

Why is temp a class member?

Don't use single line blocks. Surround them with {}

if (i > mid) {
    a[k] = temp[j++];
}

Conventions in boudaries is that the low bound is inclusive and the upper bound is exclusive (in your code both are inclusive.) By changing this, you can drop the -1, +1 and <=:

sort(a, 0, a.length);
// ...
sort(a, mid, hi);
// ...
for(int k = lo;k < hi; k++){

Overall, fix your formating. For example:

for (int k = lo; k < hi; k++) {

Try to replace Object by T, or by Comparable to avoid the need for casting.

You are sorting in a, then copying to temp, then merging back into a. It is not optimal.

I don't quite like private constructors to prevent instanciation. I would use an abstract class.