public class MergeSort
{
public static Boolean merge(Integer array[], Integer begin, Integer mid, Integer end)
{
  if ((null == array) ||
   (array.length == 0) ||
   (begin < 0) ||
   (end >= array.length) ||
   (!((begin <= mid) && (mid < end))))
  {
   return false;
  }
  Integer temp = 0;
  Integer index1 = 0;
  Integer index2 = 0;
  Integer index3 = begin;
  Integer size1 = mid - begin + 1;
  Integer size2 = end - mid;
  Integer array1[] = new Integer[size1];
  Integer array2[] = new Integer[size2];
  for (index1 = 0; index1 < size1; ++index1)
  {
   array1[index1] = array[index1 + begin];
  }
  for (index2 = 0; index2 <size2; ++index2)
  {
   array2[index2] = array[mid + 1 + index2];
  }
  index1 = 0;
  index2 = 0;
  index3 = begin;
  while ((index1 < size1) && (index2 < size2))
  {
   if (array1[index1] > array2[index2])
   {
    array[index3] = array2[index2];
    ++index2;
   }
   else
   {
    array[index3] = array1[index1];
    ++index1;
   }
   ++index3;
  }
  if (index1 == size1)
  {
   index1 = index2;
   size1 = size2;
   array1 = array2;
  }
  while (index1 < size1)
  {
   array[index3] = array1[index1];
   ++index1;
   ++index3;
  }
  return true;
}
public static Boolean sort(Integer array[], Integer begin, Integer end)
{
  if ((null == array) || (array.length == 0) || (begin < 0) || (end >= array.length) || (begin > end))
  {
   return false;
  }
  else
  {
   if (begin == end)
   {
    return true;
   }
   if ((begin + 1) == end)
   {
    if (array[begin] > array[end])
    {
     Integer temp = array[begin];
     array[begin] = array[end];
     array[end] = temp;
    }
    return true;
   }
   else
   {
    sort(array, begin, (begin + end) / 2);
    sort(array, (begin + end + 2) / 2, end);
    merge(array, begin, (begin + end) / 2, end);
    return true;
   }
  }
}
public static Boolean sort(Integer array[])
{
  if((null == array) || (array.length == 0))
  {
   return false;
  }
  return sort(array, 0, array.length - 1);
}
public static void main(String args[])
{
  Integer array[] = { 3, 6, 1,34,2,7,12,90,34,102,334,683,2,-12,45};
  MergeSort.sort(array);
  for(Integer i : array)
  {
   System.out.println(" " + i);
  }
}
}

public class MergeSort
{
public static Boolean merge(Integer array[], Integer begin, Integer mid, Integer end)
{
  if ((null == array) ||
   (array.length == 0) ||
   (begin < 0) ||
   (end >= array.length) ||
   (!((begin <= mid) && (mid < end))))
  {
   return false;
  }
  Integer temp = 0;
  Integer index1 = 0;
  Integer index2 = 0;
  Integer index3 = begin;
  Integer size1 = mid - begin + 1;
  Integer size2 = end - mid;
  Integer array1[] = new Integer[size1];
  Integer array2[] = new Integer[size2];
  for (index1 = 0; index1 < size1; ++index1)
  {
   array1[index1] = array[index1 + begin];
  }
  for (index2 = 0; index2 <size2; ++index2)
  {
   array2[index2] = array[mid + 1 + index2];
  }
  index1 = 0;
  index2 = 0;
  index3 = begin;
  while ((index1 < size1) && (index2 < size2))
  {
   if (array1[index1] > array2[index2])
   {
    array[index3] = array2[index2];
    ++index2;
   }
   else
   {
    array[index3] = array1[index1];
    ++index1;
   }
   ++index3;
  }
  if (index1 == size1)
  {
   index1 = index2;
   size1 = size2;
   array1 = array2;
  }
  while (index1 < size1)
  {
   array[index3] = array1[index1];
   ++index1;
   ++index3;
  }
  return true;
}
public static Boolean sort(Integer array[], Integer begin, Integer end)
{
  if ((null == array) || (array.length == 0) || (begin < 0) || (end >= array.length) || (begin > end))
  {
   return false;
  }
  else
  {
   if (begin == end)
   {
    return true;
   }
   if ((begin + 1) == end)
   {
    if (array[begin] > array[end])
    {
     Integer temp = array[begin];
     array[begin] = array[end];
     array[end] = temp;
    }
    return true;
   }
   else
   {
    sort(array, begin, (begin + end) / 2);
    sort(array, (begin + end + 2) / 2, end);
    merge(array, begin, (begin + end) / 2, end);
    return true;
   }
  }
}
public static Boolean sort(Integer array[])
{
  if((null == array) || (array.length == 0))
  {
   return false;
  }
  return sort(array, 0, array.length - 1);
}
public static void main(String args[])
{
  Integer array[] = { 3, 6, 1,34,2,7,12,90,34,102,334,683,2,-12,45};
  MergeSort.sort(array);
  for(Integer i : array)
  {
   System.out.println(" " + i);
  }
}
}