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: System.out.println("\n\n"
25: + "Merge Sort\n"
26: + "==========\n\n"
27: + "This program counts how many operations it takes "
28: + "for merge sort to sort a\nreversed array "
29: + "of various sizes, "
30: + "and compares that result to the expected value\n"
31: + "of 5N log(N) / 2.");
33: int len = 0;
34: do {
35: System.out.println();
36: System.out.printf("%10s %10s %10s%n",
37: "Length", "Operations", "Expected");
38: for (int i = 1; i <= 10; ++i) {
39: // create an array of random integers
40: ++len;
41: int[] numbers = makeReversedArray(len);
43: // sort it
44: int result = mergeSort(numbers, 0, len);
46: // report operation count
47: System.out.printf("%10d %10d %10d%n",
48: len, result, expected(len));
49: }
50: } while (userContinue());
51: }
53: /**
54: * Make an array of the given length, with the numbers 1 .. {@code length}
55: * in reverse order. This is the worst case for sorting for many methods.
56: *
57: * @param length the length of the array to create
58: * @return an array containing the numbers from {@code length} down to 1
59: */
60: private static int[] makeReversedArray(int length) {
61: int[] result = new int[length];
62: for (int i = 0; i < length; ++i) {
63: result[i] = length - i;
64: }
65: return result;
66: }
68: /**
69: * Sort part of an array using the merge sort algorithm,
70: * showing the steps of the algorithm.
71: *
72: * @param arr the array to be (partially) sorted
73: * @param lo the lower bound of the part to sort
74: * @param hi the upper bound of the part to sort
75: */
76: public static int mergeSort(int[] arr, int lo, int hi) {
77: // for counting operations
78: int count = 0;
80: // calculate length of part to be sorted
81: int length = hi - lo;
83: // if there's more than one element to be sorted
84: if (length > 1) {
85: // split the range in two equal parts
86: int halfLength = length / 2;
87: int mid = lo + halfLength;
89: // mergesort each half separately
90: count += mergeSort(arr, lo, mid);
91: count += mergeSort(arr, mid, hi);
93: // merge the sublists and print out the result
94: count += merge(arr, lo, mid, hi);
95: }
97: return count;
98: }
100: /**
101: * Merge two adjacent sublists of an array.
102: *
103: * Preconditions:
104: * <ul>
105: * <li> arr[lo..mid) is sorted in ascending order
106: * <li> arr[mid..hi) is sorted in ascending order
107: * </ul>
108: * Postconditions:
109: * <ul>
110: * <li> arr[lo..hi) has the same elements it had before
111: * <li> arr[mid..hi) is sorted in ascending order
112: * </ul>
113: *
114: * @param arr the array whose parts are to be merged
115: * @param lo the beginning of the lower sublist
116: * @param mid the beginning of the upper sublist
117: * @param hi the upper bound of the upper sublist
118: */
119: public static int merge(int[] arr, int lo, int mid, int hi) {
120: int count = 0;
121: int[] firstHalf = Arrays.copyOfRange(arr, lo, mid);
122: int[] lastHalf = Arrays.copyOfRange(arr, mid, hi);
123: int[] result = Arrays.copyOfRange(arr, lo, hi);
124: count += merge(result, firstHalf, lastHalf);
125: for (int i = 0; i < result.length; ++i) {
126: ++count;
127: arr[lo+i] = result[i];
128: }
129: return count;
130: }
132: /**
133: * Merge two arrays into a third.
134: *
135: * Preconditions:
136: * <ul>
137: * <li> onePart is sorted in ascending order
138: * <li> otherPart is sorted in ascending order
139: * </ul>
140: * Postconditions:
141: * <ul>
142: * <li> result has the elements of onePart and otherPart combined
143: * <li> result is sorted in ascending order
144: * </ul>
145: *
146: * @param result the merged array
147: * @param onePart one of the arrays to be merged
148: * @param otherPart the other of the arrays to be merged
149: */
150: public static int merge(int[] result,
151: int[] onePart,
152: int[] otherPart) {
153: int count = 0;
154: int i = 0;
155: int j = 0;
156: int k = 0;
158: // merge until one list runs out
159: while (j < onePart.length && k < otherPart.length) {
160: ++count;
161: if (onePart[j] < otherPart[k]) {
162: ++count;
163: result[i] = onePart[j];
164: i++;
165: j++;
166: }
167: else {
168: ++count;
169: result[i] = otherPart[k];
170: i++;
171: k++;
172: }
173: }
175: // add all remaining items from onePart
176: while (j < onePart.length) {
177: ++count;
178: result[i] = onePart[j];
179: i++;
180: j++;
181: }
183: // add all remaining items from otherPart
184: while (k < otherPart.length) {
185: ++count;
186: result[i] = otherPart[k];
187: i++;
188: k++;
189: }
191: return count;
192: }
194: /**
195: * Ask the user if they'd like to continue.
196: *
197: * @return true if the user wants to continue; false otherwise
198: */
199: private static boolean userContinue() {
200: System.out.print("\nPress ENTER to continue or N or Q to quit: ");
201: return KBD.nextLine().isEmpty();
202: }
204: /**
205: * Calcuilate how many operations we'd expect for insertion sort in the worst
206: * case.
207: *
208: * @param len the length of the list
209: * @return the expected number of operations for insertion-sorting a list of
210: * the given length
211: */
212: private static int expected(int len) {
213: return (int)Math.ceil(5 * len * Math.log(len)/Math.log(2) / 2);
214: }
216: }