class MergeSort {

  public static void merge(int[] A, int[] B, int[] C) {
    int markerA = 0;
    int markerB = 0;
    //int markerC = 0;

    while((markerA < A.length) || (markerB < B.length)) {
      int markerC = markerA + markerB;
      if(markerA == A.length) {
	C[markerC] = B[markerB];
	markerB++;
	continue;
      }
      if(markerB == B.length) {
	C[markerC] = A[markerA];
	markerA++;
	continue;
      }
      if(A[markerA] < B[markerB]) {
	C[markerC] = A[markerA];
	markerA++;
      } else {
	C[markerC] = B[markerB];
	markerB++;
      }
    } // End while()

  } // End merge()

  public static void printArray(int[] A) {
    for(int i = 0; i < A.length; i++) {
      System.out.print("    "+A[i]+",");
    } // End for(i)
    System.out.println();
  } // End printArray()

  public static void copyArray(int[] dst, int dst_start,
			       int[] src, int src_start,
			       int length) {
    for(int i = 0; i < length; i++) {
      dst[dst_start+i] = src[src_start+i];
    }
  } // End copyArray()

  public static void mergeSort(int[] P) {
    if(P.length == 1) { return; }
    int[] A = new int[P.length/2];
    int[] B = new int[P.length - A.length];

    copyArray(A, 0, P, 0, A.length);
    copyArray(B, 0, P, A.length, B.length);

    mergeSort(A);
    mergeSort(B);

    merge(A, B, P);
  } // End mergeSort()

  public static void main(String[] args) {

    int[] A = {1, 5, 9, 11};
    int[] B = {3, 4, 10};
    int[] C = new int[A.length + B.length];

    merge(A, B, C);
    printArray(C);

    int[] P = {3, 8, 2, 0};
    mergeSort(P);
    printArray(P);

  } // End main()

} // End class MergeSort