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