public List<Integer> mergeSort(List<Integer> list) { // Base case // If list has one (or less) element, return list as is int size = list.size(); if (size <= 1) { return list; }
// Partition list in half
int m = size / 2;
List<Integer> left = new ArrayList<Integer>();
List<Integer> right = new ArrayList<Integer>();
for (int i = 0; i < m; i++) {
left.add(list.get(i));
}
for (int i = m; i < size; i++) {
right.add(list.get(i));
}
// Recursively merge sort each partition
left = mergeSort(left);
right = mergeSort(right);
// If the last element of the left partition is greater than the first element of the right partition
// The left and right partitions need to be rearranged
if (left.get(left.size() - 1) > right.get(0)) {
return merge(left, right);
// Otherwise left and right partitions are in the correct order
} else {
left.addAll(right);
return left;
}
}
protected List<Integer> merge(List<Integer> left, List<Integer> right) {
List<Integer> result = new ArrayList<Integer>();
// While both containers are non-empty
// Move lesser elements to the front of the result, and remove them from their containers
while (!left.isEmpty() && !right.isEmpty()) {
if (left.get(0) < right.get(0)) {
result.add(left.remove(0));
} else {
result.add(right.remove(0));
}
}
// The container that still has elements contains elements greater than those in the other container
// It is assumed that the elements in the container are also already sorted
// So the non-empty container's elements should be appended to the end of the list
if (!left.isEmpty()) {
result.addAll(left);
} else {
result.addAll(right);
}
return result;
}This condition is going to be true most of the time:
left.get(left.size() - 1) > right.get(0)
For the case of nearly sorted lists, it could be an important optimization. But to say that the original mergesort is incorrect is not true.