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
