Java Reference
In-Depth Information
if (l2.size() == 0) {
result . addAll( l1 ) ;
return result ;
if (l1.get(0) > l2 .get(0)) {
int nextElement = l2 . get (0) ;
result .add(nextElement);
l2 .remove(0) ;
}
else {
int nextElement = l1 . get (0) ;
result .add(nextElement);
l1 .remove(0) ;
}
}
}
}
The mergeSort method it relatively straightforward. The base case is when the list has
one or zero elements. In this case, we can just return the list. Otherwise, we split the list into
two parts: firstHalf and secondHalf . We sort each half recursively and then we merge the
halves. Note that the tail recursion principle does not apply here because there are multiple
recursive calls that are not at the end of an execution path.
The merge method can also be implemented recursively as follows.
public static ArrayList < Integer > merge(ArrayList < Integer > l1 , ArrayList
< Integer > l2) {
if (l1.size() == 0) {
return l2 ;
if (l2.size() == 0) {
return l1 ;
} ArrayList < Integer > result = new ArrayList <> () ;
int nextElement ;
if (l1.get(0) > l2 .get(0))
{
nextElement = l2 . get (0) ;
l2 .remove(0) ;
}
{
nextElement = l1 . get (0) ;
l1 .remove(0) ;
result .add(nextElement);
result.addAll(merge(l1 ,l2));
return result ;
else
}
If one of the lists is exhausted, then the method returns the other list. This is the base
case. Alternatively, if there are elements in both lists, then we examine the first element of
each list. The smallest of the two values is saved in the variable nextElement and removed
from the list. As a final step, the method returns an ArrayList that contains the value of
the variable nextElement followed by recursively merging the rest of the lists. Note that
this is a case of tail recursion because there is a single recursive call that appears at the end.
Therefore, the code can be rewritten to use an infinite while loop as shown in the original
code.
Merge sort is the only algorithm in this topic that gives us good running time in the

Search WWH ::

Custom Search