Merge Sorting Lists

I'm fairly new to Java, arriving in the "future" from C and returning to type safety from Python. I'm looking for your suggestions to improve this code in the following areas:

• Correctness - are there any bugs? have I used the language correctly?

• Java conventions and idioms.

• Runtime performance.

• Generalization of input data type.

```
import java.util.ArrayList;
import java.util.List;

public class MergeSorter {

/**
* Merge sort
*
* Running time O(nlog(n))
* @param list
* @return sortedSequence
*/
public List sort(List list) {
// base case
if(list.size() leftSortedSeq = sort(list.subList(0, halfwayIndex));
List rightSortedSeq = sort(list.subList(halfwayIndex, list.size()));
return merge(leftSortedSeq, rightSortedSeq);
}

/**
* Merge step
* Running time O(n)
* @param leftSortedSeq
* @param rightSortedSeq
* @return mergedSortedSequences
*/
private List merge(List leftSortedSeq, List rightSortedSeq) {

if(leftSortedSeq.isEmpty())
return rightSortedSeq;
else if (rightSortedSeq.isEmpty())
return leftSortedSeq;

List sortedSeq = new ArrayList<>();
int lIdx = 0;
int rIdx = 0;
int leftSortedSize = leftSortedSeq.size();
int rightSortedSize = rightSortedSeq.size();
while(lIdx < leftSortedSize && rIdx < rightSortedSize) {

Integer leftSmallestElem = leftSortedSeq.get(lIdx);
Integer rightSmallestElem = rightSortedSeq.get(rIdx);
if(leftSmallestElem < rightSmallestElem) {
sortedSeq.add(leftSmallestElem);
lIdx++;
}
else {
sortedSeq.add(rightSmallestElem);
rIdx++;
}
}

// copy over remainder from both seqs
sortedSeq.addAll(leftSortedSeq.subList(lIdx, leftSortedSize));
sortedSeq.addAll(rightSortedSeq.subList

Your four questions are good ones:
Correctness - are there any bugs?

I can't see any significant bugs. There are lesser potential bugs which relate to unexpected input (for example, null lists, or lists with null members (each of those will throw NullPointerExceptions)
Correctness - I used the language correctly?

For the most part, it is neat, and well structured. Your names and conventions are good. Yout use of the sublist is uncommon but creative, and useful.

The few places where there are problems are technically functional, but, for example, this line here is concerning:

if(leftSmallestElem < rightSmallestElem) {

Here you have two Integer instances, and the comparison is a ` instances instead of ArrayList instances, and this is a good thing. Many 'novices' pass concrete, rather than interface types.

You have JavaDoc, and I always like seeing that. Unfortunately the details are very sparse in it. It's not worth having if it is not useful.

You have used private, and public appropriately.

My only real concern here is that methods are not static. There is no reason to link these methods to a specific instance of MergeSorter. Making the methods static would mean that you call them with:

List sorted = MergeSorter.sort(unsorted);

One other thing, I would expect that the sort method does an in-place sort. This is only because I am more familiar with that from the Java API. Retuning a new instance of sorted data is not wrong, just odd. Note, that for small (and empty) inputs, you return the same instance as the one you sort. This difference in behaviour is problematic. I would return a new instance on the small sorts as well as the large ones, or alternatively, just copy the results back in to the source at the end, and not return anything (in-place sort).
Runtime performance.

The performance problem you have here is significant. Using an ArrayList in the recursion you have, implies that you will be creating a lot of ArrayList instances.

The other performance issue is that you have is in your algorithm. Typically, the merge sort is done in to a single equal-sized 'buffer' as the input. You merge the small blocks from the input to the buffer, then you swap them, and merge the larger blocks back in to the original, and keep swapping the buffers, until you have a result from the top merge.
Generalization of input data type.

This is the open question.

If you bring your input data down to the lowest common denominator of the Comparable class, you could create a method:

public static > List sort(List) {
}

and then, in each place where you have the generic type Integer, you replace it with T, then you can sort any Java class with a natural order (Numbers, Strings, etc.)

The solution will need to use the compareTo mechanism, not the <` comparison. I mentioned that earlier.

StackExchange Code Review Q#67173, answer score: 7