That's what I'm saying. It's a minor optimization of the mergesort algorithm, and it's not the usual way that mergesort is presented. And I'm skeptical that it's really an optimization. Have you benchmarked it?
This condition is going to be true most of the time:
left.get(left.size() - 1) > right.get(0)
As the lists get longer (where this optimization could pay off), the condition is more and more likely to be true.
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.
This condition is going to be true most of the time:
As the lists get longer (where this optimization could pay off), the condition is more and more likely to be true.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.