public class MergeSort
1: import java.util.Scanner;
2: import java.util.Arrays;
4: /**
5: * A class to demonstrate merge sort.
6: *
7: * @author Mark Young (A00000000)
8: */
9: public class MergeSort {
11: /** biggest number in list */
12: private static final int BIGGEST = 1000;
14: /** keyboard scanner for whole program */
15: private static final Scanner kbd = new Scanner(System.in);
17: /**
18: * Demonstrate the merge sort algorithm.
19: *
20: * @param args (ignored!)
21: */
22: public static void main(String[] args) {
23: // introduce the program
24: printIntroduction();
25: pause();
27: // get and show original array
28: int[] anArray = makeIntArray();
29: System.out.println("\nArray values before sorting:");
30: PrintTrace.printArray(anArray);
31: pause();
32:
33: // sort the array
34: mergeSort(anArray, 0, anArray.length);
36: // show result of sorting
37: System.out.println("\nArray values after sorting:");
38: PrintTrace.printArray(anArray);
39: pause();
41: // check for a mistake in the sorting code
42: if (!sorted(anArray)) {
43: System.err.println("Oops! That didn't work!");
44: }
45: }
47: /**
48: * Print an introduction to this program.
49: */
50: private static void printIntroduction() {
51: System.out.print("\n\n"
52: + "Naive Merge Sort\n"
53: + "----------------\n\n"
54: + "This program demonstrates using the MergeSort algorithm "
55: + "in its simplest version.\n\n"
56: + "Original Program: Mark Young (A00000000)");
57: }
59: /**
60: * Create an array of random numbers.
61: *
62: * @return an array (size chosen by the user) of numbers in the range
63: * [0, BIGGEST).
64: */
65: private static int[] makeIntArray() {
66: // get size from user
67: System.out.print("How long should I make the list? ");
68: int numElts = kbd.nextInt();
69: kbd.nextLine();
71: // create and return array
72: int[] anArray = new int[numElts];
73: for (int i = 0; i < numElts; i++) {
74: anArray[i] = (int)(BIGGEST * Math.random());
75: }
76: return anArray;
77: }
79: /**
80: * Sort part of an array using the merge sort algorithm,
81: * showing the steps of the algorithm.
82: *
83: * @param arr the array to be (partially) sorted
84: * @param lo the lower bound of the part to sort
85: * @param hi the upper bound of the part to sort
86: */
87: public static void mergeSort(int[] arr, int lo, int hi) {
88: // calculate length of part to be sorted
89: int length = hi - lo;
91: // if there's more than one element to be sorted
92: if (length > 1) {
93: // report the range that's being sorted
94: System.out.println("Sorting from " + lo + " to " + hi + "...");
96: // split the range in two equal parts
97: int halfLength = length / 2;
98: int mid = lo + halfLength;
100: // mergesort each half separately
101: mergeSort(arr, lo, mid);
102: mergeSort(arr, mid, hi);
104: // print out the sublists before merging
105: System.out.println("Merging lists:");
106: PrintTrace.printArray(arr, lo, mid);
107: System.out.println("and:");
108: PrintTrace.printArray(arr, mid, hi);
110: // merge the sublists and print out the result
111: merge(arr, lo, mid, hi);
112: System.out.println("Gives:");
113: PrintTrace.printArray(arr, lo, hi);
115: // report the range that's been sorted
116: System.out.println("List sorted from " + lo + " to " + hi + ".");
118: // pause to let user view the merge step
119: pause();
120: }
121: }
123: /**
124: * Merge two adjacent sublists of an array.
125: *
126: * Preconditions:
127: * <ul>
128: * <li> arr[lo..mid) is sorted in ascending order
129: * <li> arr[mid..hi) is sorted in ascending order
130: * </ul>
131: * Postconditions:
132: * <ul>
133: * <li> arr[lo..hi) has the same elements it had before
134: * <li> arr[mid..hi) is sorted in ascending order
135: * </ul>
136: *
137: * @param arr the array whose parts are to be merged
138: * @param lo the beginning of the lower sublist
139: * @param mid the beginning of the upper sublist
140: * @param hi the upper bound of the upper sublist
141: */
142: public static void merge(int[] arr, int lo, int mid, int hi) {
143: int[] firstHalf = Arrays.copyOfRange(arr, lo, mid);
144: int[] lastHalf = Arrays.copyOfRange(arr, mid, hi);
145: int[] result = Arrays.copyOfRange(arr, lo, hi);
146: merge(result, firstHalf, lastHalf);
147: for (int i = 0; i < result.length; ++i) {
148: arr[lo+i] = result[i];
149: }
150: }
152: /**
153: * Merge two arrays into a third.
154: *
155: * Preconditions:
156: * <ul>
157: * <li> onePart is sorted in ascending order
158: * <li> otherPart is sorted in ascending order
159: * </ul>
160: * Postconditions:
161: * <ul>
162: * <li> result has the elements of onePart and otherPart combined
163: * <li> result is sorted in ascending order
164: * </ul>
165: *
166: * @param result the merged array
167: * @param onePart one of the arrays to be merged
168: * @param otherPart the other of the arrays to be merged
169: */
170: public static void merge(int[] result,
171: int[] onePart,
172: int[] otherPart) {
173: int i = 0;
174: int j = 0;
175: int k = 0;
177: // merge until one list runs out
178: while (j < onePart.length && k < otherPart.length) {
179: if (onePart[j] < otherPart[k]) {
180: result[i] = onePart[j];
181: i++;
182: j++;
183: }
184: else {
185: result[i] = otherPart[k];
186: i++;
187: k++;
188: }
189: }
191: // add all remaining items from onePart
192: while (j < onePart.length) {
193: result[i] = onePart[j];
194: i++;
195: j++;
196: }
198: // add all remaining items from otherPart
199: while (k < otherPart.length) {
200: result[i] = otherPart[k];
201: i++;
202: k++;
203: }
204: }
206: /**
207: * Wait for the user to press the enter key.
208: */
209: public static void pause() {
210: System.out.print("\n...Press ENTER...");
211: kbd.nextLine();
212: System.out.println();
213: }
215: /**
216: * Check whether the given array is sorted.
217: *
218: * @param arr the array to check
219: * @return true if arr is sorted; false otherwise
220: */
221: private static boolean sorted(int[] arr) {
222: for (int i = 1; i < arr.length; ++i) {
223: if (arr[i - 1] > arr[i]) {
224: return false;
225: }
226: }
227: return true;
228: }
230: }