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: * @version 2015-03-27
9: */
10: public class MergeSort {
12: /** biggest number in list */
13: private static final int BIGGEST = 1000000;
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: System.out.print("\n\n"
24: + "Naive Merge Sort\n"
25: + "----------------\n\n"
26: + "This program demonstrates using the MergeSort algorithm "
27: + "in its simplest version.\n\n");
29: System.out.print("How long should I make the list? ");
30: int numElts = kbd.nextInt();
31: kbd.nextLine();
32: int[] anArray = new int[numElts];
33: for (int i = 0; i < numElts; i++)
34: anArray[i] = (int)(BIGGEST * Math.random());
36: System.out.println("\nArray values before sorting:");
37: printArray(anArray);
38: pause();
40: mergeSort(anArray, 0, anArray.length);
42: System.out.println("\nArray values after sorting:");
43: printArray(anArray);
44: pause();
45: }
47: /**
48: * Sort part of an array using the merge sort algorithm,
49: * showing the steps of the algorithm.
50: *
51: * @param a the array to be (partially) sorted
52: * @param lo the lower bound of the part to sort
53: * @param hi the upper bound of the part to sort
54: *
55: * @post a is sorted in the range [lo..hi)
56: * and the steps of the algorithm have been printed out
57: */
58: public static void mergeSort(int[] a, int lo, int hi) {
59: // calculate length of part to be sorted
60: int length = hi - lo;
62: // if there's more than one element to be sorted
63: if (length > 1) {
64: // report the range that's being sorted
65: System.out.println("Sorting from " + lo + " to " + hi + "...");
67: // split the range in two equal parts
68: int halfLength = length / 2;
69: int mid = lo + halfLength;
71: // mergesort each half separately
72: mergeSort(a, lo, mid);
73: mergeSort(a, mid, hi);
75: // print out the sublists before merging
76: System.out.println("Merging lists:");
77: printArray(a, lo, mid);
78: System.out.println("and:");
79: printArray(a, mid, hi);
81: // merge the sublists and print out the result
82: merge(a, lo, mid, hi);
83: System.out.println("Gives:");
84: printArray(a, lo, hi);
86: // report the range that's been sorted
87: System.out.println("List sorted from " + lo + " to " + hi + ".");
89: // pause to let user view the merge step
90: pause();
91: }
92: }
94: /**
95: * Merge two adjacent sublists of an array. The method assumes
96: * that those two sublists are already sorted.
97: *
98: * @param a the array whose parts are to be merged
99: * @param lo the beginning of the lower sublist
100: * @param mid the beginning of the upper sublist
101: * @param hi the upper bound of the upper sublist
102: *
103: * @pre a[lo..mid) is sorted in ascending order
104: * and a[mid..hi) is sorted in ascending order
105: * @post a[lo..hi) contains all the same elements it did before
106: * but is sorted in ascending order
107: */
108: public static void merge(int[] a, int lo, int mid, int hi) {
109: int[] firstHalf = Arrays.copyOfRange(a, lo, mid);
110: int[] lastHalf = Arrays.copyOfRange(a, mid, hi);
111: int[] result = Arrays.copyOfRange(a, lo, hi);
112: merge(result, firstHalf, lastHalf);
113: for (int i = 0; i < result.length; ++i) {
114: a[lo+i] = result[i];
115: }
116: }
118: /**
119: * Merge two arrays into a third.
120: *
121: * @param result the merged array
122: * @param onePart one of the arrays to be merged
123: * @param otherPart the other of the arrays to be merged
124: *
125: * @pre onePart is sorted in ascending order
126: * and otherPart is sorted in ascending order
127: * @post result contains the combined elements of onePart and otherPart
128: * but is sorted in ascending order
129: */
130: public static void merge(int[] result,
131: int[] onePart,
132: int[] otherPart) {
133: int i = 0;
134: int j = 0;
135: int k = 0;
136: while (j < onePart.length && k < otherPart.length) {
137: if (onePart[j] < otherPart[k]) {
138: result[i] = onePart[j];
139: i++;
140: j++;
141: } else {
142: result[i] = otherPart[k];
143: i++;
144: k++;
145: }
146: }
147: while (j < onePart.length) {
148: result[i] = onePart[j];
149: i++;
150: j++;
151: }
152: while (k < otherPart.length) {
153: result[i] = otherPart[k];
154: i++;
155: k++;
156: }
157: }
159: /**
160: * Print the elements of an array in a nice table.
161: *
162: * @param arr the array to print
163: */
164: public static void printArray(int[] arr) {
165: printArray(arr, 0, arr.length);
166: }
168: /** number of numbers printed per line */
169: private static final int PER_LINE = 8;
170: /** number of spaces per number */
171: private static final int SPACES = 79 / PER_LINE;
172: /** format string for numbers */
173: private static final String NUM_FORMAT = "%," + SPACES + "d";
174: /** format string for place fillers */
175: private static final String STR_FORMAT = "%" + SPACES + "s";
177: /**
178: * Print an array showing only the numbers in one part of it.
179: * Numbers before the starting point/after the ending point
180: * are replaced with "filler".
181: *
182: * @param arr the array to print
183: * @param lo positions less than lo are "filled"
184: * @param hi positions hi and greater are "filled"
185: */
186: public static void printArray(int[] arr, int lo, int hi) {
187: int thisLine = 0;
188: for (int i = 0; i < arr.length; i++) {
189: if (thisLine == PER_LINE) {
190: System.out.println();
191: thisLine = 0;
192: }
193: if (lo <= i && i < hi) {
194: System.out.printf(NUM_FORMAT, arr[i]);
195: } else {
196: System.out.printf(STR_FORMAT, "...");
197: }
198: ++thisLine;
199: }
200: System.out.println();
201: }
203: /**
204: * Wait for the user to press the enter key.
205: */
206: public static void pause() {
207: System.out.print("\n...Press ENTER...");
208: kbd.nextLine();
209: System.out.println();
210: }
212: }