1 /**
2 The sort method of this class sorts an array, using the merge
3 sort algorithm.
4 */
5 public class MergeSorter
6 {
7 /**
8 Sorts an array, using merge sort.
9 @param a the array to sort
10 */
11 public static void sort(int[] a)
12 {
13 if (a.length <= 1) { return; }
14 int[] first = new int[a.length / 2];
15 int[] second = new int[a.length - first.length];
16 // Copy the first half of a into first, the second half into second
17 for (int i = 0; i < first.length; i++)
18 {
19 first[i] = a[i];
20 }
21 for (int i = 0; i < second.length; i++)
22 {
23 second[i] = a[first.length + i];
24 }
25 sort(first);
26 sort(second);
27 merge(first, second, a);
28 }
29
30 /**
31 Merges two sorted arrays into an array
32 @param first the first sorted array
33 @param second the second sorted array
34 @param a the array into which to merge first and second
35 */
36 private static void merge(int[] first, int[] second, int[] a)
37 {
38 int iFirst = 0; // Next element to consider in the first array
39 int iSecond = 0; // Next element to consider in the second array
40 int j = 0; // Next open position in a
41
42 // As long as neither iFirst nor iSecond is past the end, move
43 // the smaller element into a
44 while (iFirst < first.length && iSecond < second.length)
45 {
46 if (first[iFirst] < second[iSecond])
47 {
48 a[j] = first[iFirst];
49 iFirst++;
50 }
51 else
52 {
53 a[j] = second[iSecond];
54 iSecond++;
55 }
56 j++;
57 }
58
59 // Note that only one of the two loops below copies entries
60 // Copy any remaining entries of the first array
61 while (iFirst < first.length)
62 {
63 a[j] = first[iFirst];
64 iFirst++; j++;
65 }
66 // Copy any remaining entries of the second half
67 while (iSecond < second.length)
68 {
69 a[j] = second[iSecond];
70 iSecond++; j++;
71 }
72 }
73 }