Java Reference
In-Depth Information
The complete program containing the merge sort code follows. Its
main
method con-
structs a sample array and sorts it using the algorithm:
1 // This program implements merge sort for arrays of integers.
2
import
java.util.*;
3
4
public class
MergeSort {
5
public static void
main(String[] args) {
6
int
[] list = {14, 32, 67, 76, 23, 41, 58, 85};
7 System.out.println("before: " + Arrays.toString(list));
8 mergeSort(list);
9 System.out.println("after : " + Arrays.toString(list));
10 }
11
12 // Places the elements of the given array into sorted order
13 // using the merge sort algorithm.
14 // post: array is in sorted (nondecreasing) order
15
public static void
mergeSort(
int
[] a) {
16 if (a.length > 1) {
17 // split array into two halves
18
int
[] left = Arrays.copyOfRange(a, 0, a.length / 2);
19
int
[] right = Arrays.copyOfRange(a, a.length / 2,
20 a.length);
21
22 // recursively sort the two halves
23 mergeSort(left);
24 mergeSort(right);
25
26 // merge the sorted halves into a sorted whole
27 merge(a, left, right);
28 }
29 }
30
31 // Merges the given left and right arrays into the given
32 // result array.
33 // pre : result is empty; left/right are sorted
34 // post: result contains result of merging sorted lists;
35
public static void
merge(
int
[] result,
int
[] left,
int
[] right) {
36
int
i1 = 0; // index into left array
37
int
i2 = 0; // index into right array
38
for
(
int
i = 0; i < result.length; i++) {
39
if
(i2 >= right.length || (i1 < left.length &&
40
left[i1] <= right[i2])) {
Search WWH ::
Custom Search