# Mergesort.java

Below is the syntax highlighted version of Mergesort.java from §1.4 Analysis of Algorithms.

```/******************************************************************************
*  Compilation:  javac Mergesort.java
*  Execution:    java Mergesort N
*  Dependencies: StdOut.java StdRandom.java
*
*  Generate N pseudo-random numbers between 0 and 1 and mergesort them.
*
******************************************************************************/

public class Mergesort {

private static double[] merge(double[] a, double[] b) {
double[] c = new double[a.length + b.length];
int i = 0, j = 0;
for (int k = 0; k < c.length; k++) {
if      (i >= a.length) c[k] = b[j++];
else if (j >= b.length) c[k] = a[i++];
else if (a[i] <= b[j])  c[k] = a[i++];
else                    c[k] = b[j++];
}
return c;
}

public static double[] mergesort(double[] input) {
int N = input.length;
if (N <= 1) return input;
double[] a = new double[N/2];
double[] b = new double[N - N/2];
for (int i = 0; i < a.length; i++)
a[i] = input[i];
for (int i = 0; i < b.length; i++)
b[i] = input[i + N/2];
return merge(mergesort(a), mergesort(b));
}

/***************************************************************************
*  Check if array is sorted - useful for debugging.
***************************************************************************/
private static boolean isSorted(double[] a) {
for (int i = 1; i < a.length; i++)
if (a[i] < a[i-1]) return false;
return true;
}

// generate N real numbers between 0 and 1, and mergesort them
public static void main(String[] args) {
int N = Integer.parseInt(args[0]);
double[] a = new double[N];
for (int i = 0; i < N; i++)
a[i] = StdRandom.uniformDouble();
a = mergesort(a);
for (int i = 0; i < N; i++)
StdOut.println(a[i]);

StdOut.println(isSorted(a));
}
}

```