public class MergeSort
1: //MergeSort.java
2:
3: /**
4: * Class for sorting an array of integers from smallest to largest
5: * using the merge sort algorithm.
6: */
7: public class MergeSort
8: {
9: private static int mergeCount = 0;
10: /**
11: Precondition: Every indexed variable of the array a has a value.
12: Postcondition: a[0] <= a[1] <= ... <= a[a.length - 1].
13: */
14: public static void mergeSort
15: (
16: int[] a
17: )
18: {
19: if (a.length >= 2)
20: {
21: int halfLength = a.length / 2;
22: int[] firstHalf = new int[halfLength];
23: int[] lastHalf = new int[a.length - halfLength];
24: divide(a, firstHalf, lastHalf);
25: //Exercise:
26: //What happens if you interchange the following two lines of code?
27: mergeSort(firstHalf);
28: mergeSort(lastHalf);
29: merge(a, firstHalf, lastHalf);
30: //The following three lines display the merge number and values:
31: System.out.print("Merge #" + ++mergeCount + ": ");
32: for (int i : a) System.out.print(i + " ");
33: System.out.println();
34: }
35: //else do nothing. a.length == 1, so a is sorted.
36: }
37:
38: //Precondition: a.length = firstHalf.length + lastHalf.length.
39: //Postcondition: All the elements of a are divided
40: //between the arrays firstHalf and lastHalf.
41: private static void divide
42: (
43: int[] a, //in
44: int[] firstHalf, //out
45: int[] lastHalf //out
46: )
47: {
48: for (int i = 0; i < firstHalf.length; i++)
49: firstHalf[i] = a[i];
50: for (int i = 0; i < lastHalf.length; i++)
51: lastHalf[i] = a[firstHalf.length + i];
52: }
53:
54: //Precondition:
55: //Arrays firstHalf and lastHalf are sorted from smallest to largest
56: //a.length = firstHalf.length + lastHalf.length.
57: //Postcondition:
58: //Array a contains all the values from firstHalf and lastHalf
59: //and is sorted from smallest to largest.
60: private static void merge
61: (
62: int[] a, //out
63: int[] firstHalf, //in
64: int[] lastHalf //in
65: )
66: {
67: int firstHalfIndex = 0, lastHalfIndex = 0, aIndex = 0;
68:
69: while ((firstHalfIndex < firstHalf.length) &&
70: (lastHalfIndex < lastHalf.length))
71: {
72: if (firstHalf[firstHalfIndex] < lastHalf[lastHalfIndex])
73: {
74: a[aIndex] = firstHalf[firstHalfIndex];
75: firstHalfIndex++;
76: }
77: else
78: {
79: a[aIndex] = lastHalf[lastHalfIndex];
80: lastHalfIndex++;
81: }
82: aIndex++;
83: }
84: //At this point at least one of firstHalf and lastHalf
85: //has been completely copied to a.
86:
87: //Copy rest of firstHalf, if any.
88: while (firstHalfIndex < firstHalf.length)
89: {
90: a[aIndex] = firstHalf[firstHalfIndex];
91: aIndex++;
92: firstHalfIndex++;
93: }
94:
95: //Copy rest of lastHalf, if any.
96: while (lastHalfIndex < lastHalf.length)
97: {
98: a[aIndex] = lastHalf[lastHalfIndex];
99: aIndex++;
100: lastHalfIndex++;
101: }
102: }
103: }