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