A Practical Guide to Data Structures and Algorithms using Java

Array Data Structure 145

PositionalCollection

2

1110 9 7 6 4 3

0 1 2 3 4

5

6 7

4 10 6 3 211 9 7

4 6 210 3 9 711

11 6 210 3 7 9 4

Figure 11.3

An illustration of merge sort when run on an array of eight elements. The top array shown is the original array,

and the bottom row shown the sorted array. At each level of recursion the subarrays independently considered

are marked by the solid black lines. The braces are used to show which subarrays are merged at the next level.

i--; //move to the left

}

put(i+1, value); //put object into place

}

version.increment(); //invalidate active markers for iteration

}

}

Correctness Highlights: First, clearly this is correct ...