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