Recursion - Learning Java Through Games - page 336

14.4.6 Merge Sort
The main shortcoming of the quick sort algorithm is that its running time is unpre-
dictable. For some sequences, the algorithm can perform really fast. However, if the original
numbers are close to being sorted, then the algorithm will not perform that well. The main
problem with quick sort is that it does not guarantee that the two lists are of roughly equal
size. The merge sort algorithm is similar to the quick sort algorithm. However, at each step
it splits the array into two lists that are of roughly equal size. The certainty that the lists
are of roughly equal size comes with a price: the algorithm needs to perform an additional
merge step at every iteration.
Let us consider the following list of elements.

20 3 6 11 45 2

{ }

The merge sort algorithm will first split the array into two roughly equal halves: 20,3,6

{ }

and 11,45,2 . Next, each of the halves will be sorted recursively. The result will be the

halves: . As a final step, the two halves will be merged. At every step

of the merge, the front of each of the lists will be examined and the smallest of the two
numbers will be moved to the result. When one of the lists is exhausted, then the elements
of the other list will be moved to the result. An example implementation follows.

{ 3,6,20 } and { 2,11,45 }

import java . util . ∗ ;

public class MergeSort {
public static void main(String args [])

{

int [] a = { 20, 3, 6, 11, 45, 2 } ;
ArrayList < Integer > list = new ArrayList <> () ;
for ( int el : a) {

list .add(el);
list = mergeSort(list);
System.out.println(list);

}

public static ArrayList < Integer > mergeSort(ArrayList < Integer > a) {

if (a. size() < =1) {
return a;
} ArrayList

< Integer > firstHalf = new ArrayList <> () ;

ArrayList < Integer > secondHalf = new ArrayList <> () ;

for ( int i=0;i < a . s i z e ( ) / 2 ; i ++) {

firstHalf .add(a.get(i));
for ( int i=a.size()/2;i < a . s i z e ( ) ;

i ++) {

secondHalf .add(a. get( i )) ;
return merge(mergeSort( firstHalf ) , mergeSort(secondHalf )) ;

}

public static ArrayList < Integer > merge(ArrayList < Integer > l1 ,
ArrayList < Integer > l2) {
ArrayList < Integer > result = new ArrayList <> () ;
while ( true ) {
if (l1.size() == 0) {
result . addAll( l2 ) ;
return result ;