import java.lang.*;
import java.net.*;
import java.io.*;
import java.util.*;

/** 
 * @class Merge
 * @author Christoph W. Kessler
 *
 * NestStep source program for a 
 * parallel recursive mergesort algorithm,
 * applied to an array of N integers.
 */

public class Merge
{
  final static int N = 1000000;   // problem size


  public static int[] subArray( int[] a, int size, int offset )
  {
    int[] ret = new int[size];
    System.arraycopy( a, offset, ret, 0, size );
    return ret;
  }


  public static int[] seqmerge( int[] a, int[] b )
  {
     int n = a.length + b.length;
     int[] r = new int[n];
     int u = 0;
     int v = 0;
     int i = 0;
     while (u < a.length && v < b.length)
        if (a[u] <= b[v] 
            r[i++] = a[u++];
        else
            r[i++] = b[v++];
     for ( ; u<a.length; u++)
        r[i++] = a[u];
     for ( ; v<b.length; v++)
        r[i++] = b[v];
     return r;
  }


  public static int[] seqmergesort( int[] a )  
  {
     int n = a.length;
     if (n==1) return a;
     int[] a1 = subArray( a, n/2, 0 );
     int[] a2 = subArray( a, n-n/2, n/2 );
     int[] s1 = seqmergesort( a1 );
     int[] s2 = seqmergesort( a2 );
     int[] r = seqmerge( s1 , s2 );
     return r; 
  }


  public static sh int[] merge( sh int[] a, sh int[] b ) // merge two arrays
  {
     int n = a.length + b.length;
     sh int[] r = new sh int[n];
     int u = 0;
     int v = 0;
     int i = 0;
     while (u < a.length && v < b.length)
        if (a[u] <= b[v] 
            r[i++] = a[u++];
        else
            r[i++] = b[v++];
     for ( ; u<a.length; u++)
        r[i++] = a[u];
     for ( ; v<b.length; v++)
        r[i++] = b[v];
     return r;
  }


  public static sh int[] mergesort( sh int[] a )  
  {
     int n = a.length;
     if (n==1) return a;
     if (#==1)
         return seqmergesort( a );
     sh s1[] = null;
     sh s2[] = null;

     step( 2 ) {
        if (@==0) {
           sh int[] a1 = subArray( a, n/2, 0 );
           s1 = mergesort( a1 ); 
        }
        else {
           sh int[] a2 = subArray( a, n-n/2, n/2 );
           s2 = mergesort( a2 ); 
        }
     } 
     combine( s1, s2 );

     sh int[] r = merge( s1 , s2 );   // computation replicated

     return r; 
  }


  public static void main( String argv[] )
  {
     sh int[] arr = new sh int[N];   // arr is a replicated array:
     for (int i=0; i<N; i++) 
        arr[i] = N-i;          // initialize array

     long l = System.currentTimeMillis();  // start clock
     sh int[] res = mergesort( arr ); 
     // the computed result array is replicated 
     long ll = System.currentTimeMillis();  // stop clock
     
     if (N < 20) {
      for (int i=0; i<res.length; i++)   // print result:
        System.out.print(" " + res[i] );
      System.out.println("");
     }
     System.out.println(NestStep.PID+" ---- Time: "+ (ll-l) + " msecs");
      
  }
}