public class Merge
{
  static int howMany = 0;
  public static void mergeSort(int a[], int n)
  {
    if(n == 1)
      return;
    int a1[] = new int[n/2];
    int a2[] = new int[n - n/2];
    int where = 0;
    for(int i = 0; i < n/2; i++)
    {
      a1[where] = a[i];
      where++;
    }
    where = 0;
    for(int i = n/2; i < n; i++)
    {
      a2[where] = a[i];
      where++;
    }
System.out.print("a:");
printArray(a, n);
System.out.print("a1:");
printArray(a1, n/2);
System.out.print("a2:");
printArray(a2, n-n/2);
    mergeSort(a1, n/2);
    mergeSort(a2, n-n/2);

    int i1 = 0;
    int i2 = 0;
    int i = 0;

    while(i1 < n/2 && i2 < n-n/2)
    {
      howMany++;
      if(a1[i1] < a2[i2])
      {
        a[i] = a1[i1];
        i++;
        i1++;
      }
      else
      {
        a[i] = a2[i2];
        i++;
        i2++;
      }
    }
    while(i < n)
    {
      if(i1 == n/2)
      {
        a[i] = a2[i2];
        i2++;
        i++;
      }
      else
      {
        a[i] = a1[i1];
        i1++;
        i++;
      }
    }
  }

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

  public static void main(String args[])
  {
    int x[] = {10, 12, 8, 4, 2, 3, 7, 14, 0};
    System.out.println("Before sorting:");
    printArray(x, x.length);
    mergeSort(x, x.length);
    printArray(x, x.length);
    System.out.println("howMany = " + howMany);
  }
}