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