This is a Natural Merge Sort program from my textbook. It works, but I don't think it's good.
// Natural merge sort program in the textbook
public class NaturalMergeSortProgram {
public static void main(String[] args)
{
int a[] = new int[10000000];
int b[] = new int[a.length];
for (int i = 0; i < a.length; i++)
a[i] = (int)(1+Math.random()*(1000-1+1));
long starTime=System.currentTimeMillis();
NaturalMergeSort(a, b);
long endTime=System.currentTimeMillis();
long Time = endTime - starTime;
System.out.println("executing time: "+Time+"(ms)");
/*for (int i = 0; i < b.length; i++)
{ if (i % 20 == 0)
System.out.println();
System.out.print(a[i]+" ");
}*/
}
public static void NaturalMergeSort(int a[], int b[])
{ // merge array a into b and then b into a until sorted
while (!MergeRuns(a, b) & !MergeRuns(b, a));
}
public static boolean MergeRuns(int a[], int b[])
{
int i = 0, k = 0;
int n = a.length;
boolean asc = true;
int x;
while (i < n)
{
k = i;
do
x = a[i++];
while (i < n && x <= a[i]); // elements are increasing
while (i < n && x >= a[i]) // elements are decreasing
x = a[i++];
merge(a, b, k , i-1, asc);
asc = !asc;
}
return k == 0;
}
public static void merge(int a[], int b[], int low, int high, boolean asc)
{ // merge a[low:high] into b[low:high]
int k = asc ? low : high;
int c = asc ? 1 : -1;
int i = low, j = high;
while (i <= j)
{
if (a[i] <= a[j])
b[k] = a[i++];
else
b[k] = a[j--];
k += c;
}
}
}
Or maybe I don't get it? Because it's rather obscure and lack of comments( these comments are all added by me).
So I decide to write my own Natural Merge Sort program:
// My own natural merge sort program
public class MyNaturalMergeSort { public static void main(String args[]) {
int a[] = new int[10000000];
int b[] = new int[a.length];
for (int i = 0; i < a.length; i++)
a[i] = (int)(1+Math.random()*(1000-1+1)); long starTime=System.currentTimeMillis();
while (!NaturalMergeSort(a, b) && !NaturalMergeSort(b, a));
long endTime=System.currentTimeMillis();
long Time = endTime - starTime;
System.out.println("executing time: "+Time+"(ms)");
for (int i = 0; i < 100; i++)
{ if (i % 20 == 0)
System.out.println();
System.out.print(a[9999*i]+" ");
}
System.out.println(a[a.length-1]);
} public static boolean NaturalMergeSort(int x[], int y[]) {
// find the two adjacent natural increasing arrays x[l:m] and x[m+1:r],
// then merge them into y[l:r] using function merge()
int i, l = 0, m = 0, r;
for (i = 0; i < x.length; i++)
{ l = i;
while ((i < x.length-1) && (x[i] <= x[i+1])) // get x[l:m]
i++;
m = i++;
while ((i < x.length-1) && (x[i] <= x[i+1])) // get x[m+1:r]
i++;
r = (i == x.length) ? i-1 : i; // if it's true, that means array x is
// already sorted, we only need to copy
// array x to array y
merge(x, y, l, m, r);
}
return (l == 0) && (m == x.length - 1); // it's true only when the whole
// array is already sorted
} public static void merge(int x[], int y[], int l, int m, int r) {
// merge x[l:m] and x[m+1:r] into y[l:r]
int i = l,
j = m+1,
k = l;
while ((i <= m) && (j <= r))
if (x[i] <= x[j])
y[k++] = x[i++];
else
y[k++] = x[j++];
while (k <= r)
if (i > m) // elements in x[l:m] are all merged into array y[]
y[k++] = x[j++];
else
y[k++] = x[i++]; }
}
After running each program for 3 times, I got the executing time as below:
program in textbook -- 1457ms 1389ms 1359ms
my program -- 1281ms 1172ms 1185ms
In average, my program saves roughly 0.2 second. Though it's not that better, it still makes me exciting!
And through this practice, I came to know there's a lot of fun hacking the algorithm. I'm looking forword to write more beautiful and efficient code!