Searching and Sorting - Building Java Programs: A Back to Basics Approach - page 805

i2++;

}

}

Here is a trace of the eight steps to merge the two subarrays into a sorted array:

Subarrays Next include Merged array

123 123 123 567

0 0 0 4

14 from left

14 32 67 76 23 41 58 85 14

i1 i2 i

0 123 0 123 0 123 4 567

23 from right

14 32 67 76 23 41 58 85 14 23

i1 i2 i

0 123 0 123 0 123 4 567

32 from left

14 32 67 76 23 41 58 85 14 23 32

i1 i2 i

0 123 0 123 0 123 4 567

41 from right 14 32 67 76 23 41 58 85 14 23 32 41

i1 i2 i

0 123 0 123 0 123 4 567

58 from right 14 32 67 76 23 41 58 85 14 23 32 41 58

i1 i2 i

0 123 0 123 0 123 4 567

67 from left

14 32 67 76 23 41 58 85 14 23 32 41 58 67

i1 i2 i

0 123 0 123 0 123 4 567

76 from left

14 32 67 76 23 41 58 85 14 23 32 41 58 67 76

i1 i2 i

0 123 0 123 0 123 4 567

85 from right 14 32 67 76 23 41 58 85 14 23 32 41 58 67 76 85

i2 i