SORTING - Introduction to Java Programming: Comprehensive Version - page 868

5 // Merge sort the first half
6 int [] firstHalf = new int [list.length / 2 ];
7 System.arraycopy(list, 0 , firstHalf, 0 , list.length / 2 );
8 mergeSort(firstHalf); sort first half

9
10 // Merge sort the second half
11 int secondHalfLength = list.length - list.length / 2 ;
12 int [] secondHalf = new int [secondHalfLength];
13 System.arraycopy(list, list.length / 2 ,
14 secondHalf, 0 , secondHalfLength);
15

mergeSort(secondHalf); sort second half

16
17 // Merge firstHalf with secondHalf into list

18 merge(firstHalf, secondHalf, list);

merge two halves

19 }
20 }
21
22

/** Merge two sorted lists */

23 public static void merge( int [] list1, int [] list2, int [] temp) {

24 int current1 = 0 ; // Current index in list1

25 int current2 = 0 ; // Current index in list2

26 int current3 = 0 ; // Current index in temp

27
28 while (current1 < list1.length && current2 < list2.length) {

29 if (list1[current1] < list2[current2])

30 temp[current3++] = list1[current1++];

list1 to temp

31 else

32 temp[current3++] = list2[current2++];

list2 to temp

33 }
34
35

while (current1 < list1.length) rest of list1 to temp

36 temp[current3++] = list1[current1++];

37
38 while (current2 < list2.length)

rest of list2 to temp

39 temp[current3++] = list2[current2++];

40 }
41
42 /** A test method */
43 public static void main(String[] args) {
44 int [] list = { 2 , 3 , 2 , 5 , 6 , 1 , -2 , 3 , 14 , 12 };
45 mergeSort(list);
46 for ( int i = 0 ; i < list.length; i++)
47 System.out.print(list[i] + " " );
48 }
49 }

The mergeSort method (lines 3-20) creates a new array firstHalf , which is a copy of
the first half of list (line 7). The algorithm invokes mergeSort recursively on firstHalf
(line 8). The length of the firstHalf is list.length / 2 and the length of the secondHalf
is list.length - list.length / 2 . The new array secondHalf was created to contain
the second part of the original array list . The algorithm invokes mergeSort recursively on
secondHalf (line 15). After firstHalf and secondHalf are sorted, they are merged to
list (line 18). Thus, array list is now sorted.
The merge method (lines 23-40) merges two sorted arrays list1 and list2 into array
temp . current1 and current2 point to the current element to be considered in list1 and
list2 (lines 24-26). The method repeatedly compares the current elements from list1
and list2 and moves the smaller one to temp . current1 is increased by 1 (line 30) if
the smaller one is in list1 and current2 is increased by 1 (line 32) if the smaller one is