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: /**
10: * Precondition: Every indexed variable of the array a has a value.
11: * Postcondition: a[0] <= a[1] <= ... <= a[a.length - 1].
12: */
13: public static void sort(int[] a)
14: {
15: if (a.length >= 2)
16: {
17: int halfLength = a.length / 2;
18: int[] firstHalf = new int[halfLength];
19: int[] lastHalf = new int[a.length-halfLength];
20: divide(a, firstHalf, lastHalf);
21: sort(firstHalf);
22: sort(lastHalf);
23: merge(a, firstHalf, lastHalf);
24: }
25: //else do nothing. a.length == 1, so a is sorted.
26: }
27:
28: //Precondition: a.length = firstHalf.length + lastHalf.length.
29: //Postcondition: All the elements of a are divided
30: //between the arrays firstHalf and lastHalf.
31: private static void divide
32: (
33: int[] a,
34: int[] firstHalf,
35: int[] lastHalf
36: )
37: {
38: for (int i = 0; i < firstHalf.length; i++)
39: firstHalf[i] = a[i];
40: for (int i = 0; i < lastHalf.length; i++)
41: lastHalf[i] = a[firstHalf.length + i];
42: }
43:
44: //Precondition: Arrays firstHalf and lastHalf are sorted from
45: //smallest to largest; a.length = firstHalf.length + lastHalf.length.
46: //Postcondition: Array a contains all the values from firstHalf
47: //and lastHalf and is sorted from smallest to largest.
48: private static void merge
49: (
50: int[] a,
51: int[] firstHalf,
52: int[] lastHalf
53: )
54: {
55: int firstHalfIndex = 0, lastHalfIndex = 0, aIndex = 0;
56:
57: while ((firstHalfIndex < firstHalf.length) &&
58: (lastHalfIndex < lastHalf.length))
59: {
60: if (firstHalf[firstHalfIndex] < lastHalf[lastHalfIndex])
61: {
62: a[aIndex] = firstHalf[firstHalfIndex];
63: firstHalfIndex++;
64: }
65: else
66: {
67: a[aIndex] = lastHalf[lastHalfIndex];
68: lastHalfIndex++;
69: }
70: aIndex++;
71: }
72: //At least one of firstHalf and lastHalf has been
73: //completely copied to a.
74:
75: //Copy rest of firstHalf, if any.
76: while (firstHalfIndex < firstHalf.length)
77: {
78: a[aIndex] = firstHalf[firstHalfIndex];
79: aIndex++;
80: firstHalfIndex++;
81: }
82:
83: //Copy rest of lastHalf, if any.
84: while (lastHalfIndex < lastHalf.length)
85: {
86: a[aIndex] = lastHalf[lastHalfIndex];
87: aIndex++;
88: lastHalfIndex++;
89: }
90: }
91: }