Java Reference
In-Depth Information
Complete Program
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