Source of MergeSort.java


  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: }