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 sort
15: (
16: int[] a //inout
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: sort(firstHalf);
26: sort(lastHalf);
27: merge(a, firstHalf, lastHalf);
28: System.out.print("Merge #" + ++mergeCount + ": ");
29: for (int i : a) System.out.print(i + " ");
30: System.out.println();
31: }
32: //else do nothing. a.length == 1, so a is sorted.
33: }
34:
35: //Precondition: a.length = firstHalf.length + lastHalf.length.
36: //Postcondition: All the elements of a are divided
37: //between the arrays firstHalf and lastHalf.
38: private static void divide
39: (
40: int[] a, //in
41: int[] firstHalf, //out
42: int[] lastHalf //out
43: )
44: {
45: for (int i = 0; i < firstHalf.length; i++)
46: firstHalf[i] = a[i];
47: for (int i = 0; i < lastHalf.length; i++)
48: lastHalf[i] = a[firstHalf.length + i];
49: }
50:
51: //Precondition:
52: //Arrays firstHalf and lastHalf are sorted from smallest to largest
53: //a.length = firstHalf.length + lastHalf.length.
54: //Postcondition:
55: //Array a contains all the values from firstHalf and lastHalf
56: //and is sorted from smallest to largest.
57: private static void merge
58: (
59: int[] a, //out
60: int[] firstHalf, //in
61: int[] lastHalf //in
62: )
63: {
64: int firstHalfIndex = 0, lastHalfIndex = 0, aIndex = 0;
65:
66: while ((firstHalfIndex < firstHalf.length) &&
67: (lastHalfIndex < lastHalf.length))
68: {
69: if (firstHalf[firstHalfIndex] < lastHalf[lastHalfIndex])
70: {
71: a[aIndex] = firstHalf[firstHalfIndex];
72: firstHalfIndex++;
73: }
74: else
75: {
76: a[aIndex] = lastHalf[lastHalfIndex];
77: lastHalfIndex++;
78: }
79: aIndex++;
80: }
81: //At this point at least one of firstHalf and lastHalf
82: //has been completely copied to a.
83:
84: //Copy rest of firstHalf, if any.
85: while (firstHalfIndex < firstHalf.length)
86: {
87: a[aIndex] = firstHalf[firstHalfIndex];
88: aIndex++;
89: firstHalfIndex++;
90: }
91:
92: //Copy rest of lastHalf, if any.
93: while (lastHalfIndex < lastHalf.length)
94: {
95: a[aIndex] = lastHalf[lastHalfIndex];
96: aIndex++;
97: lastHalfIndex++;
98: }
99: }
100: }